#include "shoes.h"
#include <bits/stdc++.h>
using namespace std ;
#define int long long
struct segtree{
int seg[100003] ;
void build(int id,int l,int r){
if (l==r) seg[id]=0 ;
else {
int md=(l+r)/2 ;
build(id*2,l,md) ;
build(id*2+1,md+1,r) ;
seg[id]=0 ;
}
}
void upd(int id,int l,int r,int x,int v){
if (l==r&&l==x){
seg[id]=v ;
}
else if (l>x||r<x) return ;
else {
int md=(l+r)/2 ;
upd(id*2,l,md,x,v) ;
upd(id*2+1,md+1,r,x,v) ;
seg[id]=seg[id*2]+seg[id*2+1] ;
}
}
int query(int id,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr) return seg[id] ;
else if (l>qr||r<ql) return 0 ;
else {
int md=(l+r)/2 ;
return query(id*2,l,md,ql,qr)+query(id*2+1,md+1,r,ql,qr) ;
}
}
} sss ;
bool used[100003] ;
long long count_swaps(std::vector<signed> arr) {
int n=arr.size() ;
int i,j ;
arr.insert(arr.begin(),0) ;
map<int,queue <int>> q ;
for (i = 1 ; i <= n ; i ++){
q[arr[i]].push(i) ;
}
sss.build(1,1,n) ;
for (i = 1 ; i <= n ; i ++) sss.upd(1,1,n,i,1) ;
int tt=0 ;
for (i = 1 ; i <= n ; i ++){
if (used[i]) continue ;
int x=arr[i] ;
if (x<0){
int pos=q[-x].front() ;
tt+=sss.query(1,1,n,i+1,pos-1) ;
used[pos]=1 ;
sss.upd(1,1,n,pos,0) ;
q[-x].pop() ;
}
else {
int pos=q[-x].front() ;
tt+=sss.query(1,1,n,i+1,pos-1) ;
used[pos]=1 ;
sss.upd(1,1,n,pos,0) ;
q[-x].pop() ;
tt++ ;
}
}
return tt;
}
