#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define int int64_t
vector<int> tree;
void update(int v, int rl, int rr, int pos, int x) {
if (rl == rr) {
tree[v] = x;
return;
}
int rm = (rl + rr)/2;
if (pos <= rm) update(v*2, rl, rm, pos, x);
else update(v*2+1, rm+1, rr, pos, x);
tree[v] = tree[v*2] + tree[v*2+1];
}
int querry(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return 0;
if (rl == ql && rr == qr) {
return tree[v];
}
int rm = (rl + rr) / 2;
return querry(v*2, rl, rm, ql, min(qr, rm)) + querry(v*2+1, rm+1, rr, max(rm+1, ql), qr);
}
long long count_swaps(std::vector<int32_t> s) {
vector<bool> present(s.size(), 1);
int res = 0;
tree.assign(s.size()*4, 0);
for (int i = 0; i<s.size(); i++) {
update(1, 0, s.size()-1, i, 1);
}
vector<queue<int>> nextShoe(s.size()+1);
for (int i = 0; i<s.size(); i++) {
nextShoe[s[i]+s.size()/2].push(i);
}
for (int i = 0; i<s.size(); i++) {
if (!present[i]) continue;
int price = 0;
// for (int j = i+1; j<s.size(); j++) {
// if (!present[j]) continue;
// price++;
// if (s[j] == -s[i]) {present[j] = 0; break;}
// }
price = querry(1, 0, s.size()-1, i+1, nextShoe[-s[i]+s.size()/2].front());
present[nextShoe[-s[i]+s.size()/2].front()] = 0;
present[i] = 0;
update(1, 0, s.size()-1, nextShoe[-s[i]+s.size()/2].front(), 0);
nextShoe[-s[i]+s.size()/2].pop();
nextShoe[s[i]+s.size()/2].pop();
if (s[i] < 0) price--;
res += price;
// cout << price << "\n";
}
return res;
}
