#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> poz,neg;
int n;
vector<int> par;
vector<int> st;
int sz;
int stepen(int x){
int i=0;
while((1<<i) < x)i++;
return (1<<i);
}
void postavi (int pos){
int p=pos+sz;
st[p]=1;
p/=2;
while(p>=1){
st[p]=st[2*p]+st[2*p+1];
p/=2;
}
}
int get (int l, int r){
l+=sz;
r+=sz;
int suma=0;
while(l<=r){
if(l%2==1)suma+=st[l++];
if(r%2==0)suma+=st[r--];
l/=2;
r/=2;
}
return suma;
}
long long count_swaps(vector<int> s) {
// pravimo dva niza vrednosti, gde se naleze koje cipele
n=s.size()/2;
poz.resize(n+1);
neg.resize(n+1);
for(int i=0;i<=n;i++){
poz[i].clear();
neg[i].clear();
}
for(int i=0;i<2*n;i++){
if(s[i]>0)poz[s[i]].push_back(i);
else neg[-s[i]].push_back(i);
}
// uparujemo ih, koju spajamo sa kojom
par.assign(2*n,-1);
for(int i=1;i<=n;i++){
for(int j=0;j<poz[i].size();j++){
par[poz[i][j]]=neg[i][j];
par[neg[i][j]]=poz[i][j];
}
}
//pravimo segmentno, na pocetku prazno
sz=stepen(2*n);
st.resize(2*sz);
// prolazimo kroz niz, kad naidjemo na prvu nesparen cipelu (0 u segmentnom), racunamo udaljenost do njenog para,
// (ne ukljucujuci), oduzimamo br jedinica u seg izmedju njihovih pozicija, ako su obrnute dodajemo 1, obelezavamo ih kao posecene u seg
long long ans=0ll;
for(int i=0;i<2*n;i++){
if(st[sz+i]==1)continue;
int dis=par[i]-i-1;
dis-=get(i+1,par[i]-1);
if(s[i]>0)dis++;
ans+=(long long) dis;
postavi(i);
postavi(par[i]);
}
return ans;
}
