#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2*1000*101;
int t[4*N];
void update(int v,int s,int e,int l,int r,int val){
if(l>r) return;
if(s == l && e == r){
t[v] = val;
return;
}
int m = (s+e)/2;
update(v*2,s,m,l,min(m,r),val);
update(v*2+1,m+1,e,max(l,m+1),r,val);
t[v] = t[v*2]+t[v*2+1];
}
int get(int v,int s,int e,int l,int r){
if(l>r) return 0;
if(s == l && e == r) return t[v];
int m = (s+e)/2;
return get(v*2,s,m,l,min(m,r))+
get(v*2+1,m+1,e,max(l,m+1),r);
}
long long count_swaps(std::vector<int> s) {
long long ans = 0;
map<int,list<int> > mp;
map<int,int> kl;
int n = s.size();
for(int i = 0;i<s.size();i++){
if(mp[-s[i]].size()){
kl[mp[-s[i]].front()] = i;
mp[-s[i]].pop_front();
continue;
}
mp[s[i]].push_back(i);
// update(1,0,n-1,i,i,1);
}
map<int,bool> don;
for(int i = 0;i<s.size();i++){
if(don[i]) continue;
if(!kl[i]) continue;
/*for(int j = i+1;j<s.size();j++){
if(s[j] == -s[i]){
for(int k = j;k>i+1;k--){
swap(s[k],s[k-1]);
ans++;
}
break;
}
}
if(s[i]>s[i+1]) ans++;*/
if(s[i]>0) ans++;
int pos = kl[i];
// cout<<pos<<endl;
int cnt = get(1,0,n-1,i+1,pos);
int dist = pos-i-1;
dist-=cnt;
ans+=dist;
update(1,0,n-1,pos,pos,1);
//cout<<ans<<endl;
don[pos] = 1;
}
// system("pause");
return ans;
}
