#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
struct node {
long long s, e, m, val;
node *l, *r;
node (long long _s, long long _e) {
s = _s;
e = _e;
m = (s + e)/2;
val = 0;
if (s == e) return;
l = new node(s, m);
r = new node(m+1, e);
}
void upd(long long p, long long v) {
if (s == p && s== e) {
val = v;
return;
}
if (p <= m) {
l->upd(p, v);
}
else {
r->upd(p, v);
}
val = l->val + r->val; // transition
}
long long qry(long long qs, long long qe) {
if (qs <= s && e <= qe) {
return val;
}
else if (qs > e || s > qe) {
return 0; // base case
}
else {
return l->qry(qs, qe) + r->qry(qs, qe); // transition
}
}
} *root;
void init(long long N) {
root = new node(0, N-1);
}
void update(long long P, long long V) {
root->upd(P, V);
}
long long query(long long A, long long B) {
return root->qry(A, B);
}
long long count_swaps(vector<int> arr) {
long long sideswaps = 0;
set<pair<long long, long long> > ope;
vector<pair<long long, long long> > ind;
for (long long i=0; i<arr.size(); i++) {
long long num = arr[i];
long long oth = -num;
set<pair<long long, long long> >::iterator x = ope.lower_bound(make_pair(oth, LLONG_MIN));
if (x != ope.end() && x->first == oth) {
// pair<long long, long long> wi = *x;
ope.erase(x);
ind.push_back(make_pair(min(x->second, i), max(i, x->second)));
}
else {
if (num > 0) sideswaps++;
ope.insert(make_pair(num, i));
}
}
sort(ind.begin(), ind.end());
init(arr.size());
long long sw = 0;
for (long long i=0; i<ind.size(); i++) {
long long a = ind[i].first, b = ind[i].second;
long long x = b - a - 1;
x -= query(a, b);
update(a, 1);
update(b, 1);
sw += x;
}
return sideswaps + sw;
}
