#include "shoes.h"
#include <iostream>
#include <queue>
using namespace std;
queue<int> q[200000];
bool active[200000];
int aft[200000],indx[200000],st[800000],lazy[800000];
void build(int node,int l,int r){
if(l==r){
st[node]=indx[l];
return;
}
int mid=(r+l)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
}
void update(int node,int l,int r,int L,int R){
if(lazy[node]!=0){
if(l==r) st[node]+=lazy[node];
else{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
if(l>R || r<L) return;
if(l>=L && r<=R){
if(l==r) st[node]++;
else{
lazy[node*2]++;
lazy[node*2+1]++;
}
return;
}
int mid=(r+l)/2;
update(node*2,l,mid,L,R);
update(node*2+1,mid+1,r,L,R);
}
int query(int node,int l,int r,int idx){
if(lazy[node]!=0){
if(l==r) st[node]+=lazy[node];
else{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
if(l==r) return st[node];
int mid=(r+l)/2;
if(idx<=mid) return query(node*2,l,mid,idx);
else return query(node*2+1,mid+1,r,idx);
}
long long count_swaps(vector<int> s) {
long long result=0;
int i,n=s.size(),x,y;
for(i=0;i<n;i++){
if(q[-1*s[i]+n/2].empty()) q[s[i]+n/2].push(i);
else{
x=q[-1*s[i]+n/2].front();
q[-1*s[i]+n/2].pop();
aft[x]=i;
}
indx[i]=i;
active[i]=1;
}
build(1,0,n-1);
for(i=0;i<n;i++){
if(active[i]){
x=query(1,0,n-1,i);
y=query(1,0,n-1,aft[i]);
active[aft[i]]=0;
result+=(y-x-(s[i]<0));
if(i+1<=aft[i]-1) update(1,0,n-1,i+1,aft[i]-1);
}
}
return result;
}
