#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
struct Fenwick{
vector<ll> tr;
ll n, offs;
Fenwick(ll N){
n=N+20; offs=10; tr.resize(n+1);
}
void add(ll i, ll x){
i+=offs; for (; i<=n; i+=(-i&i)) tr[i]+=x;
}
ll get(ll i){
i+=offs; ll sum=0; for (; i; i-=(-i&i)) sum+=tr[i];
return sum;
}
};
long long count_swaps(vector<int> s) {
ll n = s.size(); Fenwick tr(n);
for (ll i=0; i<n; i++) tr.add(i, 1);
map<ll, queue<ll>> proc;
for (ll i=0; i<n; i++){
proc[s[i]].push(i);
}
ll res=0;
for (ll i=0; i<n; i++){
ll cur = s[i];
if (proc[cur].empty() or proc[cur].front()!=i) continue;
if (cur>0){
auto ind = proc[-cur].front(); tr.add(ind, -1);
proc[-cur].pop(); proc[cur].pop();
res+=tr.get(ind); tr.add(i, -1);
}else{
tr.add(i, -1); auto ind = proc[-cur].front();
tr.add(ind, -1); proc[-cur].pop();
proc[cur].pop(); res+=tr.get(ind);
}
}
return res;
}
