#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
long long merge_util(vector<int> &arr, int l, int r) {
int mid = (l+r)/2;
long long cnt = 0;
int it1 = l, it2 = mid+1;
while(it2 <= r) {
while(it1 <= mid && arr[it1] < arr[it2]) it1++;
cnt += (mid+1-it1);
it2++;
}
vector<int> temp(r-l+1);
merge(arr.begin()+l, arr.begin()+mid+1, arr.begin()+mid+1, arr.begin()+r+1, temp.begin());
copy(temp.begin(), temp.end(), arr.begin()+l);
return cnt;
}
long long find_inversions(vector<int> &arr, int l, int r) {
if(r <= l) return 0ll;
int mid = (l+r)/2;
long long ans = find_inversions(arr, l, mid) + find_inversions(arr, mid+1, r);
ans += merge_util(arr, l, r);
return ans;
}
long long find_swaps(vector<int> from, vector<int> to) {
assert(from.size() == to.size());
int n = from.size();
vector<stack<int>> s(2*n + 5);
for(int ind = n-1; ind >= 0; ind--) s[to[ind]+n].push(ind);
vector<int> pos;
for(auto i:from) {
pos.push_back(s[i+n].top());
s[i+n].pop();
}
return find_inversions(pos, 0, n-1);
}
long long count_swaps(vector<int> S) {
int n = S.size();
vector<int> to;
vector<stack<int>> m(2*n + 5);
for(int i = n-1; i>=0; i--) m[S[i]+n].push(i);
vector<bool> done(n, 0);
for(int i=0; i<n; i++) {
if(!done[i]) {
done[i] = 1;
to.push_back(-abs(S[i]));
to.push_back(abs(S[i]));
m[S[i]+n].pop();
done[m[-S[i]+n].top()] = 1;
m[-S[i]+n].pop();
}
}
return find_swaps(S, to);
}
