#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MAX_N = 2e5 + 10;
queue <int> pos[MAX_N];
bool visited[MAX_N];
class FenwickTree {
private :
int N;
vector <int> fenwick;
public :
FenwickTree() {}
FenwickTree(int n) : N(n), fenwick(N + 1) {
for(int i = 1; i <= N; i++) {
update(i, 1);
}
}
void update(int idx, int val) {
for(int x = idx; x <= N; x += (x & -x)) {
fenwick[x] += val;
}
}
int query(int idx) {
int res = 0;
for(int x = idx; x > 0; x -= (x & -x)) {
res += fenwick[x];
}
return res;
}
}fw;
long long count_swaps(vector<int> s) {
int n = s.size();
fw = FenwickTree(n);
s.insert(s.begin(), 0);
for(int i = 1; i <= n; i++) {
int idx = s[i];
if(s[i] < 0) {
idx = n + s[i] + 1;
}
pos[idx].push(i);
}
long long ans = 0;
for(int i = 1; i <= n; i++) {
if(visited[i] == true) {
continue;
}
int now = s[i], nxt = n - s[i] + 1;
if(s[i] < 0) {
now = n + s[i] + 1;
nxt = -s[i];
ans--;
}
int tpos = pos[nxt].front();
ans += fw.query(tpos) - fw.query(i);
fw.update(i, 1);
fw.update(tpos, -1);
visited[i] = true;
visited[tpos] = true;
pos[now].pop();
pos[nxt].pop();
}
return ans;
}
