#include "shoes.h"
#include <bits/stdc++.h>
#define int long long
#define rint int32_t
#define vr vector<rint>
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
using namespace std;
const int N = 2e5+5;
int t[N];
void update(int idx, int val) {
idx++;
while(idx > 0 && idx < N) {
t[idx] += val;
idx += (idx & -idx);
}
}
int query(int idx) {
idx++;
int res = 0;
while(idx > 0 && idx < N) {
res += t[idx];
idx -= (idx & -idx);
}
return res;
}
int query(int l, int r) {
if(l > r) return 0;
return query(r) - query(l-1);
}
long long count_swaps(vr a) {
// find the leftest shoe that was not paired yet -> shoe x
// find the closest unpaired possible-pair for x
// add the distance between to ans
// mark both paired
int n = a.size();
vector<bool> paired(n, 0);
set<int> lefts[n+1];
set<int> rights[n+1];
F(i, 0, n) {
update(i, 1);
if(a[i] < 0) lefts[-a[i]].insert(i);
else rights[a[i]].insert(i);
}
int ans = 0;
F(i, 0, n) {
if(paired[i]) continue;
int sz = abs(a[i]);
if(a[i] < 0) {
int per = *rights[sz].begin();
//cout << i sp per << endl;
ans += query(i+1, per-1);
paired[i] = 1;
paired[per] = 1;
rights[sz].erase(per);
lefts[sz].erase(i);
update(per, -1);
update(i, -1);
} else {
int per = *lefts[sz].begin();
//cout << i sp per << endl;
ans += query(i, per-1);
paired[i] = 1;
paired[per] = 1;
lefts[sz].erase(per);
rights[sz].erase(i);
update(per, -1);
update(i, -1);
}
}
return ans;
}
