#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 300100;

int n, a[maxn], b[maxn], c[maxn << 1];

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		b[a[i]] = i;
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		db x = fabs(i - 1. * (n + 1) / 2) / n;
		int lim = max((ll)(15 / (x * x)), 100LL);
		for (int j = b[i] - 1, s = 0; j >= max(0, b[i] - lim); --j) {
			++c[s + n];
			s += (a[j] <= i ? 1 : -1);
		}
		ll res = 0;
		for (int j = b[i], s = 0; j <= min(n, b[i] + lim); ++j) {
			s += (a[j] <= i ? 1 : -1);
			res += c[-s + n] + c[-s + n + 1];
		}
		ans += res * i;
		for (int j = b[i] - 1, s = 0; j >= max(0, b[i] - lim); --j) {
			--c[s + n];
			s += (a[j] <= i ? 1 : -1);
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}