#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl "\n"
using namespace std;
ll t[800005];
void build(ll node,ll l,ll r,ll L,ll val){
if(L<l || L>r) return;
if(l==r){
t[node]=val;
return;
}
ll mid=(l+r)/2;
build(node*2,l,mid,L,val);
build(node*2+1,mid+1,r,L,val);
t[node]=t[node*2]+t[node*2+1];
}
ll query(ll node,ll l,ll r,ll L,ll R){
if(R<l || r<L) return 0;
if(L<=l && r<=R) return t[node];
ll mid=(l+r)/2;
ll x=query(node*2,l,mid,L,R);
ll y=query(node*2+1,mid+1,r,L,R);
return y+x;
}
ll count_swaps(vector<int> s){int n=s.size();ll ans=0;
unordered_map<int,vector<int> > U;
unordered_map<int,int> ma;
for(int i=0; i<n; i++){
U[s[i]].pb(i+1);
build(1,1,n,i+1,1);
}
for(int i=0; i<n; i++){
if(query(1,1,n,i+1,i+1)==0) continue;
int x=s[i];
int y=-x;
int e=U[x][ma[x]];
int f=U[y][ma[y]];
if(f<e) swap(e,f);
ll g=query(1,1,n,e+1,f-1);
if(x>0) g++;
ans+=g;
build(1,1,n,e,0);
build(1,1,n,f,0);
ma[x]++;
ma[y]++;
}
return ans;
}
