#include "shoes.h"
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const long long MAXN = 100000;
ll total = 0;
vector<queue<int> > indices(210000);
struct ST {
int n;
vector<int> seg;
ST (int N) : n(2*N), seg(4*n) {}
void update(int l, int r) {
l += n; r += n;
while (l<r) {
if(l&1) seg[l++]++;
if(r&1) seg[--r]++;
l >>= 1;
r >>= 1;
}
}
ll query(int pos) {
pos += n;
ll ret = 0;
while(pos > 0) {
ret += seg[pos];
pos >>= 1;
}
return ret;
}
};
long long count_swaps(vector<int> s) {
int n = s.size()/2;
for (int i = 0; i < s.size(); i++) {
indices[s[i]+MAXN].push(i);
}
ST tree(s.size());
int val, other, nextInd;
for(int i = 0; i < n; i++) {
val = s[2*i]; other = -val;
indices[val+MAXN].pop();
nextInd = indices[other+MAXN].front(); indices[other+MAXN].pop();
nextInd += tree.query(nextInd);
for(int j = nextInd-1; j > 2*i; j--) {
swap(s[j],s[j+1]);
total++;
}
if (s[2*i] > s[2*i+1]) total++;
tree.update(0,nextInd);
}
return total;
}
