#include "shoes.h"
#include<map>
using namespace std;
typedef long long ll;
const int TREE_SIZE=1<<18;
int tree[2*TREE_SIZE];
void upd(int i,int x){
i+=TREE_SIZE;
tree[i]=x;
while(i!=1){
i/=2;
tree[i]=tree[2*i]+tree[2*i+1];
}
}
int get(int node,int rl,int rr,int l,int r){
if(r<=rl||rr<=l)
return 0;
if(l<=rl&&rr<=r)
return tree[node];
int m=(rl+rr)/2;
int r1=get(2*node,rl,m,l,r);
int r2=get(2*node+1,m,rr,l,r);
return r1+r2;
}
int get(int l,int r){
return get(1,0,TREE_SIZE,l,r);
}
ll count_swaps(vector<int>arr){
int n=(int)arr.size();
vector<bool>alive(n,true);
for(int i=0;i<n;i++)
upd(i,1);
map<int,vector<int>>mp;
for(int i=n-1;i>=0;i--)
mp[arr[i]].push_back(i);
ll res=0;
for(int i=0;i<n;i++){
if(!alive[i])
continue;
int v=arr[i];
if(v>0)
res++;
/*for(int j=i+1;j<n;j++)
if(alive[j]&&arr[j]==-v){
i2=j;
break;
}*/
while(!alive[mp[-v].back()])
mp[-v].pop_back();
int i2=mp[-v].back();
alive[i2]=false;
upd(i2,0);
alive[i]=false;
upd(i,0);
/*for(int j=i;j<i2;j++)
res+=alive[j];*/
res+=get(i,i2);
}
return res;
}
// 1 1 -1 -1
