#include "shoes.h"
#include <vector>
#include <algorithm>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
int n;
int bit[200010];
void update(int x, int val){
for(; x <= n; x += x & (-x)) bit[x] += val;
}
int query(int x){
int ret = 0;
for(; x; x -= x & (-x)) ret += bit[x];
return ret;
}
int query(int l, int r){
if(l > r) return 0;
return query(r) - query(l - 1);
}
bitset<200010> vis;
deque<int> lf[100010], rg[100010];
long long count_swaps(vector<int> s) {
n = s.size();
int pos = 0;
for(auto &k : s){
if(k > 0) rg[k].emplace_back(++pos);
else lf[-k].emplace_back(++pos);
update(pos, 1);
}
long long ans = 0;
for(int i = 1; i <= n; i++){
// cerr << i << "\n";
if(vis[i]) continue;
vis[i] = true;
if(s[i - 1] < 0){
int idx = -s[i - 1];
lf[idx].pop_front();
int nxt = rg[idx].front(); rg[idx].pop_front();
ans += query(i + 1, nxt - 1);
update(nxt, -1);
vis[nxt] = true;
} else {
int idx = s[i - 1];
rg[idx].pop_front();
int nxt = lf[idx].front(); lf[idx].pop_front();
ans += query(i, nxt - 1);
update(nxt, -1);
vis[nxt] = true;
}
// cerr << i << " " << ans << "\n";
update(i, 0);
}
return ans;
}
