#include "shoes.h"
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int b[1000100];
int a[1000100];
int seg[4*1001000];
void sett(int s,int e,int p,int l,int r)
{
// cout<<" ? "<<endl;
if(l>e||r<s)
return ;
if(s>=l&&e<=r)
{
seg[p]++;
return ;
}
int mid=(s+e)/2;
sett(s,mid,p*2,l,r);
sett(mid+1,e,p*2+1,l,r);
return ;
}
int gett(int s,int e,int p,int i)
{
//cout<<" ! "<<endl;
if(i<s||i>e)
return 0;
if(s==e)
return seg[p];
int mid=(s+e)/2;
if(i>=s&&i<=mid)
return gett(s,mid,p*2,i)+seg[p];
else if(i>mid&&i<=e)
{
return gett(mid+1,e,p*2+1,i)+seg[p];
}
else return gett(mid+1,e,p*2+1,i)+seg[p]+gett(s,mid,p*2,i);
}
map<int,int>m;
vector<int>v[200100];
vector<int>v2[200100];
int vis[1001000];
long long count_swaps(vector<int> s) {
int n=s.size();
for(int i=0;i<n;i++)
{
a[i]=s[i];
}
for(int i=0;i<n;i++)
{//cout<<"SD";
if(a[i]>0)
v[a[i]].push_back(i);
else
v2[-a[i]].push_back(i);
} long long mn=0;
for(int i=0;i<n;i++)
{
if(vis[i])
continue;
if(a[i]<0)
{
int ii=gett(0,n-1,1,i);
ii+=i;
int y=m[-a[i]];
int jj=v[-a[i]][y];
int jjj=jj;
vis[jj]=1;
jj+=gett(0,n-1,1,jj);
m[-a[i]]++;
m[a[i]]++;
mn+=jj-ii-1;
sett(0,n-1,1,i,jjj-1);
// cout<<" "<<ii<<" "<<jj<<" "<<i<<endl;
}
else {
int ii=gett(0,n-1,1,i);
ii+=i;
int y=m[-a[i]];
int jj=v2[a[i]][y];
int jjj=jj;
vis[jj]=1;
jj+=gett(0,n-1,1,jj);
m[-a[i]]++;
m[a[i]]++;
mn+=jj-ii;
sett(0,n-1,1,0,jjj-1);
// cout<<" "<<ii<<" "<<jj<<endl;
}
// cout<<" "<<mn<<endl;
}
// cout<<gett(0,n-1,1,0)<<endl;
return mn;
}
// 4 1 -2 -3 4 2 -1 -4 3
