#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using std::cin;
using std::cout;

using ll = long long;
int n;

const int N = 300005;
int p[N];

int mem[N * 2];
int * cnt = mem + N;

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i) {
        cin >> p[i];
    }
    ll ans = 0;
    for(int i = 1;i <= n;++i) {
        ll L = n / (std::abs((p[i] - n / 2)) + 1) + 1;
        L = L * L * 6;
        int l = std::max<ll>(1, i - L), r = std::min<ll>(n, i + L);
        int sum = 0;
        const int V = p[i];
        const int R = i - l;
        int cc = 0;
        cnt[0] = 1;
        for(int j = l;j < i;++j) {
            sum += p[j] >= V ? 1 : -1;
            cnt[sum] += 1;
        }
        for(int j = i;j <= r;++j) {
            sum += p[j] >= V ? 1 : -1;
            cc += cnt[sum - 1] + cnt[sum - 2];
        }
        ans += cc * p[i];
        sum = 0;
        memset(cnt - R, 0, 4 * (R + R + 1));
//        if(i % 10000 == 0) std::cerr << i << std::endl;
    }
    cout << ans << '\n';
}