#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());
map<int, stack<int>> s;
int n = from.size();
for(int ind = n-1; ind >= 0; ind--) s[to[ind]].push(ind);
vector<int> pos;
for(auto i:from) {
pos.push_back(s[i].top());
s[i].pop();
}
return find_inversions(pos, 0, n-1);
}
long long count_swaps(vector<int> S) {
vector<int> to;
for(auto i:S) {
if(i < 0) {
to.push_back(i);
to.push_back(-i);
}
}
return find_swaps(S, to);
}
