#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int btree[4*N];
void build(int node,int l,int r)
{
if(l==r)
{
btree[node]=1;
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build((node<<1)|1,mid+1,r);
btree[node]=btree[node<<1]+btree[(node<<1)|1];
}
void update(int node,int l,int r,int ind)
{
if(r<ind||ind<l) return;
if(l==r)
{
btree[node]=0;
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,ind);
update((node<<1)|1,mid+1,r,ind);
btree[node]=btree[node<<1]+btree[(node<<1)|1];
}
int query(int node,int l,int r,int ql,int qr)
{
if(r<ql||qr<l) return 0;
if(ql<=l&&r<=qr) return btree[node];
int mid=(l+r)>>1;
return query(node<<1,l,mid,ql,qr)+query((node<<1)|1,mid+1,r,ql,qr);
}
long long count_swaps(std::vector<int> s) {
set<pair<int,int> > ss;
int n=s.size();
for(int i=0;i<n;i++)
{
ss.insert({s[i],i});
}
build(1,0,n-1);
long long ans=0;
for(int i=0;i<n;i++)
{
if(ss.find({s[i],i})==ss.end()) continue;
auto ot=*ss.lower_bound({-s[i],i});
ans+=query(1,0,n-1,i+1,ot.second-1);
ans+=s[i]>0;
update(1,0,n-1,i);
update(1,0,n-1,ot.second);
ss.erase(ot);
}
return ans;
}
