#include "shoes.h"
#include <set>
using namespace std;
#define ll long long
#define POW 20
set<int> shoes[400000];
int n;
ll segtree[(2 << POW)+1];
int l[(2 << POW)+1], r[(2 << POW)+1];
ll init_node(int node, int l1, int r1) {
l[node] = l1;
r[node] = r1;
int mid = (l1+r1)/2;
if(node<(1<<POW))
segtree[node] = init_node(2*node,l1,mid) + init_node(2*node+1,mid,r1);
return segtree[node];
}
void update_node(int node) {
if(node<(1<<POW))
segtree[node]=segtree[2*node]+segtree[2*node+1];
if(node!=1)
update_node(node/2);
}
void set_dist(int i) {
segtree[(1<<POW)+i]=0;
update_node((1<<POW)+i);
}
ll get_dist_sum(int node, int i) {
if(i<=l[node])
return 0;
if(i>=r[node])
return segtree[node];
return get_dist_sum(2*node, i) + get_dist_sum(2*node+1, i);
}
ll get_dist(int i){
return segtree[(1<<POW)+i];
}
ll count_swaps(vector<int> s) {
n = s.size();
for(int i=0;i<n;i++)
shoes[s[i]+200000].insert(i);
for(int i=0;i<n;i++)
segtree[(1<<POW) + i]=1;
init_node(1, 0, 1<<POW);
ll res=0;
int pos1=0;
while(pos1<n){
int pos2=*shoes[200000-s[pos1]].begin();
res+=get_dist_sum(1, pos2);
if(s[pos1]<0)
res--;
set_dist(pos1);
set_dist(pos2);
shoes[200000-s[pos1]].erase(shoes[200000-s[pos1]].begin());
shoes[200000+s[pos1]].erase(shoes[200000+s[pos1]].begin());
while(get_dist(pos1)==0) pos1++;
}
return res;
}
