#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct node{
int s, e, m, val;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
val=e-s+1;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void up(int ind, int nv){
if (s==e)val=nv;
else{
if (ind<=m)l->up(ind, nv);
else r->up(ind, nv);
val = l->val+r->val;
}
}
int query(int left, int right){
if (left>right)return 0;
if (s==left && e==right)return val;
if (right<=m)return l->query(left, right);
else if (left>m)return r->query(left, right);
else return l->query(left, m)+r->query(m+1, right);
}
}*st;
long long count_swaps(vector<int> vect){
long long ans=0;
st = new node(0, vect.size()-1);
vector<int> r(vect.size(), -1);
map<int, deque<int> > id;
for (int i=0; i<vect.size(); ++i){
if (id[-vect[i]].size())r[id[-vect[i]][0]]=i, id[-vect[i]].pop_front();
else id[vect[i]].pb(i);
}
for (int i=0; i<vect.size(); ++i){
if (r[i]==-1)continue;
ans+=st->query(i+1, r[i]-1);
if (vect[i]>vect[r[i]])++ans;
st->up(r[i], 0);
}
return ans;
}
