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

#define ll long long

const int N = 300005;
const int MAGIC = 125;

int p[N], n;

int sqr(int x) { return x * x; }

int pool[N << 1], *buc = pool + N;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }
    
    // n = 3e5;
    // // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // mt19937 rng(114514);
    // for (int i = 1; i <= n; i++) p[i] = i;
    // shuffle(p + 1, p + n + 1, rng);

    ll ans = 0, turns = 0;
    for (int i = 1; i <= n; i++) {
        int diff = max(1, abs(n / 2 - p[i]));
        int delta = n / diff + MAGIC;
        int cur = 0, *ptr = buc, tag = 1;
        (*ptr)++;

        for (int j = i - 1; j >= 1; j--) {
            ++turns;
            if (p[j] < p[i]) ptr--;
            else ptr++;
            (*ptr)++;
            if (abs(buc - ptr) > delta) {
                tag = j;
                break;
            }
        }
        cur = 0, ptr = buc;
        ll res = *buc + *(buc + 1);
        for (int j = i + 1; j <= n; j++) {
            ++turns;
            if (p[j] < p[i]) ptr++;
            else ptr--;
            res += *ptr + *(ptr + 1);
            if (abs(buc - ptr) > delta) break;
        }
        ans += res * p[i];

        cur = 0, ptr = buc;
        (*ptr)--;
        for (int j = i - 1; j >= tag; j--) {
            if (p[j] < p[i]) ptr--;
            else ptr++;
            (*ptr)--;
        }
    }
    cerr << "turns = " << turns << '\n';
    printf("%lld\n", ans);
    return 0;
}

/*
mt19937 rng(114514)
3e5: 6741152540127257
*/