#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn = 200020;
struct FenwickTree{
ll bit[mxn];
FenwickTree(){
memset(bit,0,sizeof(bit));
}
void add(int pos){
for(int i = pos;i<mxn;i += i&(-i))bit[i]++;
}
ll query(int pos){
ll ans = 0;
for(int i = pos;i;i-=i&(-i))ans+=bit[i];
return ans;
}
};
ll count_swaps(vector<int> A) {
int n = A.size();
map<int,vector<int> > ind;
for(int i = 0;i<n;i++){
ind[A[i]].push_back(i);
}
for(auto &i : ind)reverse(i.second.begin(),i.second.end());//Gi reversame vektorite za da imame pobrzi oparacii so pop i push back
int order[n];
for(int i = 0;i<n;i++)order[i] = 0;
for(int i = 0;i<n;i++){
if(order[i])continue;
ind[A[i]].pop_back();
if(A[i] < 0){
order[i] = i * 2 + 1;
order[ind[-A[i]].back()] = i * 2 + 2;
}else{
order[i]=i * 2 + 2;
order[ind[-A[i]].back()]=i * 2 + 1;
}
ind[-A[i]].pop_back();
}
ll ans = 0;
FenwickTree fwt;
for(int i = n-1;i>=0;i--){
ans += fwt.query(order[i] -1 );
fwt.add(order[i]);
}
return ans;
}
