#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
ll N,niz[maxn],par[maxn];
ll res=0;
map<int,queue<int>> mapa;
ll fwt[maxn];
void add(int x,int kol){
for(int i=x;i<=N;i+=(i&(-i)))
fwt[i]+=kol;
}
ll get(int x){
if(x<1)
return 0;
ll ret=0;
for(int i=x;i>=1;i-=(i&(-i)))
ret+=fwt[i];
return ret;
}
ll suma(ll l,ll r){
if(l>r)
return 0;
// cout<<l<<" "<<r<<" "<<get(l-1)<<" "<<get(r)<<endl;
return get(r)-get(l-1);
}
ll count_swaps(vector<int> s) {
N=s.size();
for(int i=0;i<N;i++)
niz[i+1]=s[i];
for(int i=1;i<=N;i++){
int sup=-niz[i];
if(mapa[sup].size()!=0){
int x=mapa[sup].front();
mapa[sup].pop();
par[x]=i;
par[i]=x;
continue;
}
mapa[niz[i]].push(i);
}
for(int i=1;i<=N;i++){
if(niz[i]==0)
continue;
if(niz[i]>0) /// Zamena leva-desna na kraju
res++;
//cout<<i<<" "<<par[i]<<endl;
res+=(par[i]-i-1);
//cout<<suma(i+1,par[i]-1)<<endl;
res-=suma(i+1,par[i]-1);
add(i,1);
add(par[i],1);
niz[i]=0;
niz[par[i]]=0;
}
return res;
}
