#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
pair<vector<int>,ll> count_inv(vector<int> v) {
int n=v.size();
if (n==1) return {v,0ll};
int mid=n/2;
ll inv=0;
vector<int> l, r;
for (int i=0;i<n;i++) {
if (i<mid) l.push_back(v[i]);
else r.push_back(v[i]);
}
pair<vector<int>,ll> res1 = count_inv(l);
vector<int> sortedL = res1.first;
inv += res1.second;
pair<vector<int>,ll> res2 = count_inv(r);
vector<int> sortedR = res2.first;
inv += res2.second;
vector<int> merged;
int lpos=0, rpos=0;
while (lpos<(int)sortedL.size() && rpos<(int)sortedR.size()) {
if (sortedL[lpos]<=sortedR[rpos]) {
merged.push_back(sortedL[lpos]);
lpos++;
inv+=rpos;
}
else if (sortedL[lpos]>sortedR[rpos]) {
merged.push_back(sortedR[rpos]);
rpos++;
}
}
while (lpos<(int)sortedL.size()){
merged.push_back(sortedL[lpos]);
lpos++;
inv+=rpos;
}
while (rpos<(int)sortedR.size()){
merged.push_back(sortedR[rpos]);
rpos++;
}
return {merged,inv};
}
long long count_swaps(std::vector<int> s) {
vector<int> order;
int n = s.size();
bool marked[n]; memset(marked,false,sizeof(marked));
multimap<int,int> mp;
int flips=0;
vector<int> disc(n);
for(int i=0;i<n;i++) {
if(mp.find(-s[i])==mp.end()) {
mp.insert({s[i],i});
disc[i]=i;
order.push_back(-abs(s[i]));
order.push_back(abs(s[i]));
}
else {
disc[i]=mp.find(-s[i])->second;
mp.erase(mp.find(-s[i]));
if(s[i]<0) {
flips++;
}
}
}
ll ans = count_inv(disc).second + flips;
return ans;
}
