Submission #3721787

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
int bit[100001], N;
int sum(int i) {
	int s = 0;
	while (i > 0) {
		s += bit[i];
		i -= i & -i;
	}
	return s;
}
void add(int i, int x) {
	while (i <= N) {
		bit[i] += x;
		i += i & -i;
	}
}
int pos[100001];
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x;
		cin >> x;
		pos[x] = i;
		add(i, 1);
	}
	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		int l = 0, r = 0;
		if (pos[i] > 1) l = sum(pos[i] - 1);
		if (pos[i] + 1 <= N) r = sum(N) - sum(pos[i]);
		if (l <= r) ans += l;
		else ans += r;
		add(pos[i], -1);
	}
	cout << ans << endl;
}

Submission Info

Judge Result