#include "shoes.h"
#include <bits/stdc++.h>
#define MAX 100010
using namespace std;
typedef long long ll;
typedef pair<ll,ll>ii;
typedef vector<ii>vi;
ll tree[800010],v[200010];
void init(int node,int a,int b){
if(a==b){
tree[node]=1;
return;
}
init(2*node+1,a,(a+b)/2);
init(2*node+2,((a+b)/2)+1,b);
tree[node]=tree[2*node+1]+tree[2*node+2];
}
void update(int node,int a,int b,int pos,int val){
if(a>pos or b<pos) return;
if(a==b){tree[node]=val; return;}
update(2*node+1,a,(a+b)/2,pos,val);
update(2*node+2,((a+b)/2)+1,b,pos,val);
tree[node]=tree[2*node+1]+tree[2*node+2];
}
int query(int node,int a,int b, int l,int r){
// cout<<node<<" "<<a<<" "<<b<<" "<<l<<" "<<r<<endl;
//return 0;
if(l>r) return 0;
if(b<l or a>r) return 0;
if(l<=a and b<=r) return tree[node];
return query(2*node+1,a,(a+b)/2,l,r)+query(2*node+2,((a+b)/2)+1,b,l,r);
}
long long count_swaps(std::vector<int> s) {
vector<vi> sz;
int n=s.size()/2;
sz.resize(MAX);
//cout<<"hi"<<endl;
for(int i=0;i<s.size();i++){
sz[abs(s[i])].push_back(ii(s[i],i));
}
// cout<<sz.size()<<endl;
ll res=0;
vector<ii>sa;
for(int i=1;i<=s.size();i++){
sort(sz[i].begin(),sz[i].end());
for(int j=0;j<sz[i].size()/2;j++){
ll l=sz[i][j].second;
ll r=sz[i][j+sz[i].size()/2].second;
if(l>r){
swap(l,r);
res++;
}
sa.push_back(ii(l,r));
}
}
// cout<<"hi"<<endl;
sort(sa.begin(),sa.end());
init(0,0,s.size()-1);
// cout<<res<<endl;
for(int i=0;i<sa.size();i++){
// cout<<sa[i].second<<" "<<sa[i].first<<endl;
int x,y;
if(sa[i].second-1>=sa[i].first+1){
x=query(0,0,s.size()-1,0,sa[i].second-1);
y=query(0,0,s.size()-1,0,sa[i].first+1);
//cout<<x<<" "<<y<<endl;
res+=abs(x-y);
}
//cout<<res<<endl;
// cout<<"hi"<<endl;
update(0,0,s.size()-1,sa[i].first,0);
/* cout<<query(0,0,s.size()-1,0,s.size())<<endl;
for(int i=0;i<40;i++){
cout<<tree[i]<<" ";
}
cout<<endl;*/
update(0,0,s.size()-1,sa[i].second,0);
/* for(int i=0;i<40;i++){
cout<<tree[i]<<" ";
}
cout<<endl;*/
}
return res;
}
