#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
int miejsce[100009][2];
vector<int>V1[100009],V2[100009];
int Tre[1000000];
int base;
void Przedzial(int l, int p, int dod)
{
l+=base;
p+=base;
while(l<=p)
{
if(l%2==1)
{
Tre[l]+=dod;
l++;
}
if(p%2==0)
{
Tre[p]+=dod;
p--;
}
l>>=1;
p>>=1;
}
}
int Punkt(int v)
{
v+=base;
int wynik=0;
while(v>0)
{
wynik+=Tre[v];
v>>=1;
}
return wynik;
}
int TworzenieDrzewa(int x)
{
int u=1;
while(x>0)
{
x>>=1;
u<<=1;
}
return u;
}
long long count_swaps(vector<int>tab)
{
long long wynik=0;
const int n=tab.size();
const int n2=n/2;
for(int i=0;i<n;i++)
{
if(tab[i]<0)
{
V1[-tab[i]].push_back(i);
}
else if(tab[i]>0)
{
V2[tab[i]].push_back(i);
}
}
for(int i=1;i<=n2;i++)
{
reverse(V1[i].begin(),V1[i].end());
reverse(V2[i].begin(),V2[i].end());
}
base=TworzenieDrzewa(n);
for(int i=0;i<n;i++)
{
Tre[i+base]=i;
}
for(int i=0;i<n;i++)
{
const int u=abs(tab[i]);
if(tab[i]<0&&(int)V1[u].size()>0&&V1[u].back()==i)
{
int u1=Punkt(V1[u].back());
int u2=Punkt(V2[u].back());
Przedzial(0,V2[u].back(),1);
wynik+=u2-u1-1;
}
else if(tab[i]>0&&(int)V2[u].size()>0&&V2[u].back()==i)
{
int u1=Punkt(V2[u].back());
int u2=Punkt(V1[u].back());
Przedzial(0,V1[u].back(),1);
wynik+=u2-u1;
}
else{continue;}
V1[u].pop_back();
V2[u].pop_back();
}
return wynik;
}
