#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long ll;
int seg[800000];
void update(ll a,ll b,ll c,ll x,ll y){
if(x<=a && b<=y){seg[c]++;return;}
ll m=(a+b)/2;
if(y<=m)update(a,m,2*c,x,y);
else if(x>=m+1)update(m+1,b,2*c+1,x,y);
else {
update(a,m,2*c,x,m);
update(m+1,b,2*c+1,m+1,y);
}
}
int findseg(ll a,ll b,ll c,ll x){
if(a==x && b==x)return seg[c];
ll m=(a+b)/2;
if(x<=m)return seg[c]+findseg(a,m,2*c,x);
else return seg[c]+findseg(m+1,b,2*c+1,x);
}
long long count_swaps(vector<int> s){
ll ans=0;
int n=s.size()/2;
memset(seg,0,sizeof(seg));
vector<int> pos[n+1],neg[n+1];
bool visited[2*n];memset(visited,false,sizeof(visited));
for(int i=2*n-1;i>=0;i--){
if(s[i]>0)pos[s[i]].PB(i);
else neg[-s[i]].PB(i);
}
for(int i=0;i<2*n;i++){
int ind=-1;
if(visited[i]==true)continue;
if(s[i]>0){
pos[s[i]].pop_back();
while(!neg[s[i]].empty()){
ind=neg[s[i]].back();
neg[s[i]].pop_back();
if(visited[ind]==false)break;
}
ans++;
}
else{
neg[-s[i]].pop_back();
while(!pos[-s[i]].empty()){
ind=pos[-s[i]].back();
pos[-s[i]].pop_back();
if(visited[ind]==false)break;
}
}
if(ind==-1)continue;
visited[i]=visited[ind]=true;
int incind=findseg(0,2*n-1,1,ind);
int inci=findseg(0,2*n-1,1,i);
ans+=(ind+incind)-(i+inci)-1;
if(ind+incind>i+inci+1)update(0,2*n-1,1,i+1,ind-1);
}
return ans;
}
