#include <iostream>
#include <stdio.h>
#include <vector>
#include "shoes.h"
//#include "grader.cpp"
using namespace std;
const long long mxn = 2e6 + 10;
vector <long long> li[mxn] = {};
long long ta[mxn] = {},se[mxn] = {},u[mxn] = {},cou[mxn] = {};
long long cre(long long cl,long long cr,long long no)
{
if(cl == cr)
{
se[no] = 1;
return 0;
}
long long mid = (cl+cr) / 2;
cre(cl,mid,no*2);
cre(mid+1,cr,no*2+1);
se[no] = se[no*2] + se[no*2+1];
return 0;
}
long long del(long long cl,long long cr,long long no,long long tn)
{
if(cr < tn || cl > tn)
{
return 0;
}
if(cl == cr)
{
se[no] = 0;
return 0;
}
long long mid = (cl+cr) / 2;
del(cl,mid,no*2,tn);
del(mid+1,cr,no*2+1,tn);
se[no] = se[no*2] + se[no*2+1];
return 0;
}
long long fisu(long long cl,long long cr,long long no,long long tn)
{
if(cl > tn)
{
return 0;
}
if(cr <= tn)
{
return se[no];
}
long long mid = (cl+cr) / 2,su = 0;
su += fisu(cl,mid,no*2,tn);
su += fisu(mid+1,cr,no*2+1,tn);
return su;
}
long long count_swaps(vector<int> s)
{
long long i,j,n = s.size(),cpo,ans = 0;
cre(0,n-1,1);
for(i=0; i<n; i++)
{
if(s[i] > 0)
{
li[s[i]*2].push_back(i);
}
else
{
li[(-s[i] * 2) + 1].push_back(i);
}
}
for(i=0; i<n; i++)
{
if(u[i] == 0)
{
if(s[i] > 0)
{
cpo = li[s[i]*2+1][cou[s[i]*2+1]];
cou[s[i]*2+1] ++;
cou[s[i]*2] ++;
ans += fisu(0,n-1,1,cpo-1);
}
else
{
cpo = li[(-(s[i]*2))][cou[-s[i]*2]];
cou[-s[i]*2] ++;
cou[(-s[i]*2)+1] ++;
ans += fisu(0,n-1,1,cpo-1)-1;
}
del(0,n-1,1,cpo);
del(0,n-1,1,i);
u[i] = 1;
u[cpo] = 1;
}
}
return ans;
}
//long long main()
//{
//
// return 0;
//}
