#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int N = 2e5 + 5;
int n;
struct Fenwick{
int tree[N];
int getsum(int r){
int sum = 0;
for(int i = r; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
int query(int l, int r){
return getsum(r) - getsum(l - 1);
}
void update(int pos, int val){
for(int i = pos; i < N; i += i & -i) tree[i] += val;
}
};
Fenwick fw;
int findcnt(vector<int> a, vector<int> b){
map<int, vector<int>> nums;
for(int i = 0; i < n; i++) nums[b[i]].push_back(i + 1);
for(int i = 0; i < n; i++){
int x = *nums[a[i]].begin(); nums[a[i]].erase(nums[a[i]].begin());
a[i] = x;
}
long long inv = 0;
for(auto x : a){
inv += fw.query(x + 1, N - 1);
fw.update(x, 1);
}
return inv;
}
long long count_swaps(vector<int> arr){
n = arr.size();
vector<bool> flag(n, false);
map<int, vector<int>> mp;
for(int i = 0; i < n; i++){
if(mp[-arr[i]].empty()) mp[arr[i]].push_back(i);
else{
flag[*mp[-arr[i]].begin()] = true;
mp[-arr[i]].erase(mp[-arr[i]].begin());
}
}
vector<int> bestarr;
for(int i = 0; i < n; i++){
if(flag[i]){
bestarr.push_back(-abs(arr[i]));
bestarr.push_back(abs(arr[i]));
}
}
return findcnt(arr, bestarr);
}
