#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10, M = 1e6 + 50;
inline int read()
{
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
struct node{
int fa[N], siz[N];
inline void initial(int n){
for(register int i = 0; i < n; i++) fa[i] = i, siz[i] = 1;
}
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y){
int fx = find(x), fy = find(y);
if(fx == fy) return;
if(siz[fx] > siz[fy]) swap(fx, fy);
fa[fx] = fy, siz[fy] += siz[fx], siz[fx] = 0;
}
}T;
int n, ans;
int L[N], R[N], arr[N];
set<int> s;
vector<int> vec[M];
inline int Get_R(int x)
{
if(x == n) return n;
return R[T.find(x)];
}
signed main()
{
memset(L, -1, sizeof(L)), memset(R, -1, sizeof(R));
n = read();
for(register int i = 0; i < n; i++) arr[i] = read();
for(register int i = 0; i < n; i++) vec[arr[i]].push_back(i);
T.initial(n);
for(register int v = 1; v <= M - 1; v++){
vector<int> ed, tem;
int res = 0;
for(register int x : s){
int r = Get_R(x);
int nexr = max(r, r == n ? -1 : Get_R(r));
if(nexr == r) ed.push_back(x);
else{
if(L[nexr] != -1) ed.push_back(x);
else L[nexr] = x, tem.push_back(nexr);
res += (nexr - r) * T.siz[T.find(x)], R[T.find(x)] = nexr;
}
}
for(register int x : ed){
s.erase(x);
if(L[Get_R(x)] == -1) L[Get_R(x)] = x;
else T.merge(L[Get_R(x)], x);
}
for(register int x : tem) L[x] = -1;
for(register int x : vec[v]){
++res, R[x] = (x + 1), s.insert(x);
if(L[x] != -1) s.insert(L[x]);
L[x] = -1;
}
ans = ans + res * v;
}
printf("%lld\n", ans);
return 0;
}
