#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int)3e5 + 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';

}
set<int> l[N];
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i], r[i] = 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;
    set<int> u;
    for(int v = 1; v <= 60; v++) {
        set<int> u1;
        for(int i:u) {
            if(r[i] != r[r[i]]) {
                u1.insert(i);
            }
            l[r[i]].erase(i);
            r[i] = r[r[i]];
            l[r[i]].insert(i);
        }
        for(int i = 1; i <= n; i++) {
            if(a[i] == v) {
                r[i] = i + 1;
                for(int j:l[i]) {
                    u1.insert(j);
                }
                l[i].clear();
            }
        }
        u1.swap(u);
        for(int i = 1; i <= n; i++) {
            d[v] += r[i] - i;
        }
        res += (d[v] - d[v - 1]) * 1ll * v;
    }
    cout << res << '\n';
}

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

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

    while(t--) 
        test();
}