#include <bits/stdc++.h>
#pragma optimize(2)
using namespace std;


using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

static const int maxn = 3e5 + 10;
static const int ZERO = 3e5 + 1;
int cntr[2][maxn << 1];

void solve() {
    // freopen("data.txt", "r", stdin);

    double prev = clock();
    ll ans = 0;
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int tl = 0;
    for (int i = 1; i <= n; i++) {
        int lsum = 0, rsum = 0;
        int l = i, r = i;
        ll res = 0;
        cntr[i & 1][ZERO]++;
        int k = max(1, abs(n / 2 - a[i]));
        int len = ll(n) * n / (ll(k) * k);
        tl += len;
        int L = max(1, i - len), R = min(n, i + len);
        while (l > L) {
            l--;
            lsum += (a[l] > a[i] ? 1 : -1);
        }
        while (r < R) {
            r++;
            rsum += (a[r] > a[i] ? 1 : -1);
            cntr[r & 1][ZERO + rsum]++;
        }
        // cout << L << ' ' << R << ' ' << lsum << ' ' << rsum << '\n';
        while (l <= i) {
            res += cntr[l & 1][ZERO - lsum];
            res += cntr[(l & 1) ^ 1][ZERO - lsum + 1];
            lsum -= (a[l] > a[i] ? 1 : -1);
            l++;
        }
        while (r >= i) {
            cntr[r & 1][ZERO + rsum]--;
            rsum -= (a[r] > a[i] ? 1 : -1);
            r--;
        }
        // cout << res << '\n';
        ans += res * a[i];
    }
    cout << ans << '\n';

    double cur = clock();
    // cout << "Time=" << (cur - prev) / CLOCKS_PER_SEC << '\n';
    // cout << "tot len=" << tl << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    while (T--)
        solve();

    return 0;
}
/*
4
1 4 2 3
77987580201049
36490923129641
*/