#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) {
ll ret = 0;
while(pos > 0) {
ret += seg[pos];
pos >>= 1;
}
return ret;
}
};
long long count_swaps(vector<int> s) {
queue<int> neg;
queue<int> pos;
for(int i = 0; i < s.size(); i++) {
if(s[i] > 0) { pos.push(i); continue; }
neg.push(i);
}
ST tree(s.size());
for(int i = 0; i < s.size()/2; i++) {
int small = neg.front(); neg.pop();
small += tree.query(small);
int big = pos.front(); pos.pop();
small += tree.query(big);
if(small > big) { swap(small,big); total++; }
total += big-small-1;
tree.update(0,big);
}
return total;
}
