#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int N=2e5;
const int PP=3e5;
vector<int> cup[2*N+10];
bool vis[N+10];
int pot;
int tree[2*PP+10];
void add_t(int l,int r,long long c)
{
for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
{
if(l%2==1)
tree[l++]+=c;
if(r%2==0)
tree[r--]+=c;
}
return;
}
long long read_t(int x)
{
long long ans=0;
for(x+=pot-1;x>0;x/=2)
ans+=tree[x];
return ans;
}
long long count_swaps(vector<int> s)
{
int n=s.size();
long long ans=0;
for(int i=n-1;i>=0;i--)
cup[N+s[i]].push_back(i+1);
for(pot=1;pot<n;pot*=2);
for(int i=1;i<=n;i++)
tree[pot+i-1]=i-1;
for(int i=1;i<=n;i++)
{
if(vis[i])
continue;
int val=s[i-1];
int j=cup[N-val].back();
//cerr<<val<<" "<<i<<" "<<j<<"\n";
cup[N+val].pop_back();
cup[N-val].pop_back();
vis[i]=vis[j]=true;
ans+=read_t(j);
if(val<0)
ans--;
add_t(i,pot,-1);
add_t(j,pot,-1);
}
return ans;
}
