#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,M=(N<<4),OO=0x3f3f3f;
int pos[N],tree[M];
void build(int node,int l,int r){
if(l==r) tree[node]=pos[l];
else{
int med=(l+r)/2;
build(node<<1,l,med);
build(node<<1|1,med+1,r);
tree[node]=tree[node<<1]+tree[node<<1|1];
}
}
void update(int node,int l,int r,int idx,int val){
if(l>r || l>idx || r<idx) return;
if(l==r) tree[node]+=val;
else{
int med=(l+r)/2;
update(node<<1,l,med,idx,val);
update(node<<1|1,med+1,r,idx,val);
tree[node]=tree[node<<1]+tree[node<<1|1];
}
}
int query(int node,int s,int e,int l,int r){
if(s>e||s>r||e<l) return 0;
if(s>=l&&e<=r) return tree[node];
int med=(s+e)/2;
int q1=query(2*node,s,med,l,r);
int q2=query(2*node+1,med+1,e,l,r);
return max(q1,q2);
}
ll count_swaps(vector<int>s){
map<int,vector<int>>m;
ll ret=0;
int n=s.size();
for(int i=0;i<n;++i)
update(1,0,n-1,i,1);
for(int i=n-1;i>=0;--i)
m[s[i]].push_back(i);
for(int i=0;i<n;++i){
if(query(1,0,n-1,0,i)-query(1,0,n-1,0,i-1)!=1) continue;
int k=m[-s[i]].back();
m[s[i]].pop_back();
m[-s[i]].pop_back();
update(1,0,n-1,i,-1);
update(1,0,n-1,k,-1);
ret+=query(1,0,n-1,0,k)-query(1,0,n-1,0,i);
if(s[i]>0) ++ret;
}
return ret;
}
