#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct Fenwick{
int n;
vector<int>a;
Fenwick(int n):n(n),a(n+10){}
void update(int i,int x){
for(;i<=n;i+=i&-i){
a[i]+=x;
}
}
int query(int i){
int res=0;
for(;i>0;i-=i&-i){
res+=a[i];
}
return res;
}
int range(int l,int r){
return query(r)-query(l);
}
};
long long count_swaps(vector<int> s) {
int n=s.size(),x;
Fenwick a(n);
ll sum=0LL;
vector<vector<int>>left(n+10),right(n+10);
for(int i=1;i<=n;++i){
if(s[i-1]<0){
left[abs(s[i-1])].emplace_back(i);
}else{
right[s[i-1]].emplace_back(i);
}
}
for(int i=1;i<=n/2;++i){
if(!left[i].empty())reverse(left[i].begin(),left[i].end());
if(!right[i].empty())reverse(right[i].begin(),right[i].end());
}
for(int i=1;i<=n;++i){
x=s[i-1];
//cout<<abs(x)<<' '<<left[abs(x)].size()<<' '<<right[abs(x)].size()<<'\n';
if(left[abs(x)].empty() or right[abs(x)].empty())continue;
if(left[abs(x)].size()>right[abs(x)].size()){
left[abs(x)].pop_back();
continue;
}else if(left[abs(x)].size()<right[abs(x)].size()){
right[abs(x)].pop_back();
continue;
}
//int now=sum;
//cout<<"--> "<<left[abs(x)].back()<<' '<<right[abs(x)].back()<<'\n';
if(x<0){
x=abs(x);
sum+=right[x].back()-left[x].back()-1-a.range(left[x].back(),right[x].back());
a.update(right[x].back(),1);
left[x].pop_back();
}else{
sum+=left[x].back()-right[x].back()-a.range(right[x].back(),left[x].back());
a.update(left[x].back(),1);
right[x].pop_back();
}
//cout<<"--> "<<sum-now<<'\n';
}
return sum;
}
/*
3
3 2 -1 -3 1 -2
3
-2 2 -2 2 -2 2
*/
