#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <unordered_map>
#define gc getchar
#define pc putchar
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )

using namespace std;

const int N = 200010;
const int mod = 998244353; int T = 1;
void read() { return; } template <typename T, typename ...T2> void read(T &s, T2 &...oth) { s = 0; char ch = gc(); bool f = 0; for (; ch < '0' or ch > '9'; ch = gc()) if (ch == '-') f = 1; for (; ch >= '0' and ch <= '9'; ch = gc()) s = (s << 1) + (s << 3) + (ch ^ 48); s = f ? -s : s; read(oth...); return; }
void write(char ch) { return; } template <typename T, typename ...T2> void write(char ch, T s, T2 ...oth) { if (!s) { pc('0'); pc(ch); write(ch, oth...); return; } int stk[100], top = 0; if (s < 0) pc('-'), s = ~s + 1; while (s) stk[ ++ top] = s % 10, s /= 10; do pc(stk[top -- ] + (1 << 4) + (1 << 5)); while (top); pc(ch); write(ch, oth...); return; }
int qpow(int a, int b = mod - 2, int s = 1) { for (; b; b >>= 1, a = a * a % mod) if (b & 1) s = s * a % mod; return s; }

const int M = 2010;
bool st[N];
int n, p[N], ans, s[N], id[N];
unordered_map<int, int> bin[M];
int lb[N], rb[N], a[N], d[N], tag[N];
int C(int n) {
	return n * (n - 1) / 2;
}
void build(int k) { // Build the kth block.
	bin[k].clear();
	rep(i, max(n / 2, lb[k]), rb[k])
		bin[k][a[i]] ++ ;
}
int calc() {
	int sum = 0;
	rep(i, d[n / 2], d[n]) {
		sum += bin[i][1 - tag[i]];
		sum += bin[i][0 - tag[i]] * C(n / 2) * 2;
	} return sum;
}
void chg(int l, int r, int v) {
	int lc = d[l], rc = d[r];
	if (lc == rc) {
		rep(i, l, r) a[i] += v;
		build(lc); return;
	}
	rep(i, l, rb[lc]) a[i] += v; build(lc);
	rep(i, lb[rc], r) a[i] += v; build(rc);
	rep(i, lc + 1, rc - 1) tag[i] += v;
}
signed main() {
	read(n);
	rep(i, 1, n) read(p[i]);
	rep(i, 1, n) id[p[i]] = i;
	rep(i, 1, n) st[i] = 0;
	rep(i, 1, n / 2) st[id[i]] = 1;
	rep(i, 1, n) s[i] = s[i - 1] + st[i];
	rep(i, n / 2, n) a[i] = s[i] - s[i - n / 2];
	int B = 500; rep(i, 1, n) d[i] = i / B;
	rep(i, 1, n) rb[d[i]] = i;
	dep(i, n, 1) lb[d[i]] = i;
	rep(i, d[n / 2], d[n]) build(i);
	rep(i, 1, n / 2 + 1) {
		ans += calc(); int p1 = id[i], p2 = id[i + n / 2];
		chg(max(p1, n / 2), min(n, p1 + n / 2 - 1), -1);
		chg(max(p2, n / 2), min(n, p2 + n / 2 - 1), 1);
	} printf("%lld\n", ans); return 0;
}