#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn = 200020;
struct FenwickTree{
ll bit[mxn];
FenwickTree(){
memset(bit,0,sizeof(bit));
}
void add(int pos){
for(int i = pos;i<mxn;i += i&(-i))bit[i]++;
}
ll query(int pos){
ll ans = 0;
for(int i = pos;i;i-=i&(-i))ans+=bit[i];
return ans;
}
};
ll count_swaps(vector<int> s) {
int n = s.size();
map<int,vector<int> > mp;
for(int i = 0;i<n;i++){
mp[s[i]].push_back(i);
}
for(auto &i : mp)reverse(i.second.begin(),i.second.end());
int d[n];
for(int i = 0;i<n;i++)d[i] = 0;
int cur = 1;
for(int i = 0;i<n;i++){
if(d[i])continue;
if(s[i] < 0){
mp[s[i]].pop_back();
d[i] = cur;
d[mp[-s[i]].back()] = cur + 1;
mp[-s[i]].pop_back();
}else{
mp[s[i]].pop_back();
d[i]=cur+1;
d[mp[-s[i]].back()]=cur;
mp[-s[i]].pop_back();
}
cur+= 2;
}
ll ans = 0;
FenwickTree fwt;
for(int i = n-1;i>=0;i--){
ans += fwt.query(d[i] -1 );
fwt.add(d[i]);
}
return ans;
}
