#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> st(2*4*100000 + 5,0);
int n;
void update(int cur, int l, int r, int tar){
if(l==r){
st[cur]=1;
}
else{
int m=(l+r)/2;
if(tar<=m){
update(cur*2,l,m,tar);
}
else{
update(cur*2+1,m+1,r,tar);
}
st[cur]=st[cur*2]+st[cur*2+1];
}
}
int query(int cur, int l, int r, int ql, int qr){
if(ql>qr){
return 0;
}
if(ql<=l && r<=qr){
return st[cur];
}
int m=(l+r)/2;
return query(cur*2,l,m,ql,min(m,qr)) + query(cur*2+1,m+1,r,max(m+1,ql),qr);
}
void update(int tar){//updates point to 1
update(1,1,2*n,tar+1);
}
int query(int ql, int qr){
return query(1,1,2*n,ql+1,qr+1);
}
long long count_swaps(vector<int> s) {
n=s.size()/2;
long long out=0;
map<int,priority_queue<int>> next;
for(int i=0;i<2*n;i++){
next[s[i]].push(-i);
}
//maps a size to the next -ve index of that size
for(int i=0;i<2*n;i++){
if(query(i,i)==1){
continue;
}
if(s[i]>0){
out++;//final swap if wrong way around
}
int ind=-next[-s[i]].top();
next[-s[i]].pop();
next[s[i]].pop();
out+=ind-i-1;
out-=query(i,ind);
update(i);
update(ind);
}
return out;
}
