#include "shoes.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <queue>
using namespace std;
vector<int>closest;
vector<long long>added(1e6, 0);
vector<bool>puesto;
int n;
void find_next(vector<int>& s){
unordered_map<int, priority_queue<int> >mapa;
for (int i=0; i<n; i++){
int siz=s[i];
if (mapa.find(-siz)!=mapa.end() and mapa[-siz].size()>0){
int ind=-mapa[-siz].top();
mapa[-siz].pop();
closest[ind]=i;
closest[i]=ind;
}else mapa[siz].push(-i);
}return;
}
long long find_pos(int p, int l, int r, int x){
if (l==r) return added[p];
int m=(l+r)/2;
if (x<=m) return added[p]+find_pos(p*2, l, m, x);
else return added[p]+find_pos(p*2+1, m+1, r, x);
}
void add(int p, int l, int r, int a, int b){
if (a<=l && b>=r){
added[p]++;
return;
}else if (b<l || a>r) return;
int m=(l+r)/2;
add(p*2, l, m, a, b);
add(p*2+1, m+1, r, a, b);
return;
}
long long count_swaps(vector<int> s) {
n=s.size();
closest.assign(n, -1);
puesto.assign(n, false);
find_next(s);
//for (int i=0; i<n; i++) cout<<closest[i]<<' ';
long long int ans=0;
for (int i=0; i<n; i++){
if (puesto[i]==true) continue;
int ind=closest[i];
puesto[i]=true;
puesto[ind]=true;
int posi=i+find_pos(1, 0, n-1, i);
int posind=ind+find_pos(1, 0, n-1, ind);
//cout<<posi<<' '<<posind<<endl;
ans=ans+posind-posi;
if (s[i]<0) ans--;
if (i+1<=ind-1) add(1, 0, n-1, i+1, ind-1);
}
return ans;
}
