#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
long int seg[600000];
void update(int s,int e,int u,int ind){
if(u<s || u>e){
return;
}
if(s==e && s==u){
seg[ind]=1;
return;
}
int mid=(s+e)/2;
update(s,mid,u,ind*2);
update(mid+1,e,u,ind*2+1);
seg[ind]=seg[ind*2]+seg[ind*2+1];
}
int query(int s,int e , int qs,int qe,int ind){
if(qs<=s && e<=qe){
return seg[ind];
}
if(qs>e || qe<s){
return 0;
}
int mid=(s+e)/2;
int p1=query(s,mid,qs,qe,ind*2);
int p2=query(mid+1,e,qs,qe,ind*2+1);
return p1+p2;
}
long long count_swaps(std::vector<int> s) {
vector < int > row;
vector < int > row2;
vector < vector < int > > l(200000,row);
vector < vector < int > > r(200000,row2);
int li[200000+1]={};
int ri[200000+1]={};
for(int i=0;i<s.size();i++){
if(s[i]>0){
r[s[i]].push_back(i);
}
else
l[-s[i]].push_back(i);
}
long long int ans=0;
/// n log n
int v[200000]={};
for(int i=0;i<s.size();i++){
long long int cou=0;
if(v[i]==1){
continue;
}
int f=-s[i];
if(f>0){
li[f]++;
int start=i;
int e=r[f][ri[f]];
ri[f]++;
int q=query(1,s.size(),start+1,e+1,1);
v[start]=1;
v[e]=1;
update(1,s.size(),start+1,1);
update(1,s.size(),e+1,1);
// cout<<q<<endl;
cou=cou + e-start-1-q;
}
else{
cou=1;
ri[-f]++;
int start=i;
int e=l[-f][li[-f]];
li[-f]++;
int q=query(1,s.size(),start+1,e+1,1);
v[start]=1;
v[e]=1;
update(1,s.size(),start+1,1);
update(1,s.size(),e+1,1);
// cout<<q<<endl;
cou=cou + e-start-1-q;
}
ans+=cou;
}
return ans;
}
