#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = s.size() / 2;
vector<queue<int>>pos(n + 1),neg(n + 1);
for (int i = 0;i<2*n;++i){
if (s[i] > 0){
pos[s[i]].push(i);
}
else{
neg[-s[i]].push(i);
}
}
int cnt = 0;
vector<int>label(2 * n);
for (int i = 0;i<2 * n;++i){
if (s[i] > 0){
if (!pos[s[i]].empty() && pos[s[i]].front() == i){
label[pos[s[i]].front()] = cnt + 1;
label[neg[s[i]].front()] = cnt;
pos[s[i]].pop();
neg[s[i]].pop();
cnt+=2;
}
}
else{
if (!neg[-s[i]].empty() && neg[-s[i]].front() == i){
label[pos[-s[i]].front()] = cnt + 1;
label[neg[-s[i]].front()] = cnt;
pos[-s[i]].pop();
neg[-s[i]].pop();
cnt+=2;
}
}
}
auto merge = [&](int left,int mid,int right){
long long ans = 0;
int i = left,j = mid + 1,k = 0;
vector<int>temp(right - left + 1);
while(i <=mid && j<=right){
if (label[i] < label[j]){
temp[k++] = label[i++];
}
else{
ans+=mid - i + 1;
temp[k++] = label[j++];
}
}
while(i<=mid){
temp[k++] = label[i++];
}
while(j<=right){
temp[k++] = label[j++];
}
int p = left;
while(left<=right){
label[left] = temp[left - p];
++left;
}
return ans;
};
function<long long(int,int)>merge_sort = [&](int left,int right){
if (left >= right)return 0LL;
long long ans = 0;
int mid = (left + right)>>1;
ans+=merge_sort(left,mid);
ans+=merge_sort(mid + 1,right);
ans+=merge(left,mid,right);
return ans;
};
return merge_sort(0,2 * n - 1);
}
