#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 300000 + 5;
const int K = 80;
const int B = 1000;

int N, a[MAX_N], pos[MAX_N];

ll solve(int mid, int lim) {
    int l = max(1, mid - lim);
    int r = min(N, mid + lim);
    static int cntl[MAX_N << 1], cntr[MAX_N << 1];
    int minv = N + 1, maxv = -N - 1;
    for (int i = mid, j = 0; i >= l; i --) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntl[j + MAX_N] ++;
        minv = min(minv, j);
        maxv = max(maxv, j);
    }
    for (int i = mid, j = 0; i <= r; i ++) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntr[j + MAX_N] ++;
    }
    ll ans = 0;
    for (int i = minv; i <= maxv; i ++) {
        ans += 1ll * cntl[i + MAX_N] * (cntr[MAX_N - i] + cntr[MAX_N - i + 1]);
    }
    for (int i = mid, j = 0; i >= l; i --) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntl[j + MAX_N] = 0;
    }
    for (int i = mid, j = 0; i <= r; i ++) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntr[j + MAX_N] = 0;
    }
    return ans * a[mid];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for (int i = 1; i <= N; i ++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    ll ans = 0;
    for (int i = 1; i <= N; i ++) {
        int x = abs(N / 2 - i) + 1;
        int lim = N / i * K + B;
        ans += solve(pos[i], lim);
    }
    cout << ans << '\n';
    cerr << "time : " << clock() << endl;
    
    return 0;
}