#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int sz = 2e5 + 10;
int st[sz];
int n;
int query(int x) {
int sm = 0;
for (; 0 < x; x -= x & -x) sm += st[x];
return sm;
}
void update(int x) {
for (; x <= n; x += x & -x) {
st[x] ++;
}
}
long long count_swaps(std::vector<int> s) {
map<int,queue<int>>cl;
n = s.size();
for (int i = 0; i < n; i ++) {
cl[s[i]].push(i);
}
long long r = 0;
for (int i = 0; i < n; i ++) {
auto it = query(i + 1) - query(i);
if (it != 0) continue;
int ix = cl[-s[i]].front();
int vs = i - query(i + 1);
int ve = ix - query(ix + 1);
r += (ve - vs);
if (s[i] < 0) {
r --;
}
cl[-s[i]].pop();
cl[s[i]].pop();
update(i + 1);
update(ix + 1);
}
return r;
}
