#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int)1e6 + 12;

int n, a[N], r[N];
ll d[N];
int dp[3001][3001], opt[3001][3001];
void solve() {
    for(int i = 1; i <= n; i++) {
        dp[i][i] = a[i];
        opt[i][i] = i;
        opt[n + 1][i] = i;
    }
    for(int i = n; i >= 1; i--) {
        for(int j = i + 1; j <= n; j++) {
            dp[i][j] = (int)1e9;
            for(int k = opt[i][j - 1]; k < min(j, opt[i + 1][j] + 1); k++) {
                int v = max(dp[i][k], dp[k + 1][j]) + 1;
                if(v < dp[i][j]) {
                    dp[i][j] = v;
                    opt[i][j] = k;
                }
            }
        }
    }
    ll res = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            res += dp[i][j];
        }
    }
    cout << res << '\n';

}
vector<int> p[N];
set<int> l[N];
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i], r[i] = i;
        p[a[i]].push_back(i);
    }
    if(n <= 3000) {
        solve();
        return;
    }
    r[n + 1] = n + 1;
    for(int i = 1; i <= n + 1; i++) {
        l[i].insert(i);
    }
    ll res = 0, s = 0;
    set<int> u;
    for(int v = 1; v <= 60; v++) {
        set<int> u1;
        s += (int)u.size();
        d[v] = d[v - 1];
        for(int i:u) {
            assert(r[i] != r[r[i]]);
            l[r[i]].erase(i);
            d[v] -= (r[i] - i);
            r[i] = r[r[i]];
            d[v] += (r[i] - i);
            l[r[i]].insert(i);
            if(r[i] != r[r[i]]) {
                u1.insert(i);
            }
        }
        for(int i:p[v]) {
            r[i] = i + 1;
            d[v]++;
            for(int j:l[i]) {
                if(r[j] == r[r[j]]) continue;
                u1.insert(j);
            }
            l[i + 1].insert(i);
            l[i].clear();
        }
        u1.swap(u);
        res += (d[v] - d[v - 1]) * 1ll * v;
    }
    // assert(s <= (int)4e6);
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) 
        test();
}