#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int N=200001;
int nn;
ll st[N*4];
void upd(int idx,int l,int r,int pos,int val){
if(l==r){
st[idx]=val;
return;
}
int mid=(l+r)>>1;
if(mid>=pos) upd(2*idx,l,mid,pos,val);
else upd(2*idx+1,mid+1,r,pos,val);
st[idx]=st[idx*2]+st[idx*2+1];
}
ll ask(int idx,int l,int r,int ql,int qr){
if(ql>r||l>qr) return 0;
else if(ql<=l&&r<=qr) return st[idx];
int mid=(l+r)>>1;
return ask(2*idx,l,mid,ql,qr)+ask(2*idx+1,mid+1,r,ql,qr);
}
ll get(int l,int r){
if(l>r) return 0;
return ask(1,0,nn-1,l,r);
}
ll count_swaps(vector<int>s)
{
int n=(int)s.size();
vector<int>next(n);
vector<int>P[n+1],N[n+1];
for(int i=0;i<n;i++){
if(s[i]>0) P[s[i]].push_back(i);
else N[-s[i]].push_back(i);
}
for(int val=1;val<=n;val++){
for(int i=0;i<P[val].size();i++){
next[P[val][i]]=N[val][i];
next[N[val][i]]=P[val][i];
}
}
nn=n;
ll res=0;
for(int i=0;i<n;i++){
if(get(i,i)) continue;
for(int j=next[i];j<=next[i];j++){
if(!get(j,j)&&s[j]==-s[i]){
if(s[i]>0) ++res;
res+=(((j-1)-(i+1)+1)-get(i+1,j-1));
upd(1,0,n-1,i,1);
upd(1,0,n-1,j,1);
break;
}
}
}
return res;
}
