#include "shoes.h"
#include <map>
using namespace std;
struct SegmentTree{
vector<int> t;
SegmentTree(int n){
t.resize(4*n+5);
}
void assign(int v, int tl, int tr, int idx, int val){
if (tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (idx <= tm) assign(v*2, tl, tm, idx, val);
else assign(v*2+1, tm+1, tr, idx, val);
t[v] = t[v*2] + t[v*2+1];
}
int getkth(int v, int tl, int tr, int k){
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
if (t[v*2] >= k) return getkth(v*2, tl, tm, k);
else return getkth(v*2+1, tm+1, tr, k - t[v*2]);
}
int sum(int v, int tl, int tr, int l, int r){
if (tl == l && tr == r) return t[v];
int tm = (tl + tr) / 2;
int res = 0;
if (l <= tm) res += sum(v*2, tl, tm, l, min(r, tm));
if (r > tm) res += sum(v*2+1, tm+1, tr, max(l, tm+1), r);
return res;
}
};
long long count_swaps(vector<int> s) {
map<int, int> mp;
int n = s.size();
SegmentTree tree(n);
for (int i = 0; i < n; ++i) {
tree.assign(1, 0, n-1, i, 1);
mp[s[i]] = i;
}
long long ans = 0;
for (int i = 0; i < n / 2; ++i) {
int x = tree.getkth(1, 0, n-1, 1);
int y = tree.sum(1, 0, n-1, 0, mp[-s[x]]) - 1;
ans += max(y - 1, 0) * 1ll;
if (s[x] > 0) ans++;
tree.assign(1, 0, n-1, x, 0);
tree.assign(1, 0, n-1, mp[-s[x]], 0);
}
return ans;
}
