#include<bits/stdc++.h>
using namespace std;
#include "shoes.h"
#define F first
#define S second
#define MID ((l+r)/2)
int seg[700000];
int n;
void build(int l=0, int r=n, int ind=1){
if(l==r) seg[ind] = 1;
else{
build(l, MID, ind*2);
build(MID+1, r, ind*2+1);
seg[ind] = seg[ind*2] + seg[ind*2+1];
}
}
void update(int p, int l=0, int r=n, int ind=1){
if(l==r && l==p) seg[ind] = 0;
else if(r<p || l>p || l==r) return;
else{
update(p, l, MID, ind*2);
update(p, MID+1, r, ind*2+1);
seg[ind] = seg[ind*2] + seg[ind*2+1];
}
}
int query(int rl, int rr, int l=0, int r=n, int ind=1){
if(rl<=l && r<=rr) return seg[ind];
else if(r<rl || l>rr) return 0;
else return query(rl, rr, l, MID, ind*2) + query(rl, rr, MID+1, r, ind*2+1);
}
long long count_swaps(std::vector<int> s) {
n = s.size();
build();
int swaps=0;
int ind = 0;
unordered_map<int, vector<int> > m;
for(int i=0;i<s.size();i++){
m[s[i]].push_back(i);
}
while(ind<s.size()){
if(m[s[ind]].size()==0 || m[s[ind]][0]!=ind){
ind++;
continue;
}
if(s[ind]>0) swaps++;
if(m[-s[ind]].size()==0) while(1) {}
int i = m[-s[ind]][0];
//cout<<ind<<" "<<i<<endl;
//cout<<query(ind, i)<<endl;
//cout<<(i-ind-1)<<endl;
//cout<<endl;
swaps += query(ind, i) - 2;
//swaps += (i-ind-1);
update(m[s[i]][0]);
//cout<<query(ind, i)<<endl;
m[-s[ind]].erase(m[s[i]].begin());
m[s[ind]].erase(m[s[ind]].begin());
ind++;
//cout<<endl<<endl<<endl;
}
return swaps;
}
