#include "shoes.h"
#define int long long
using namespace std;
template<int e> struct segtree {
vector<int> v, a;
void resz(int n, vector<int> w) {v.assign(4*n,e); a = w;}
void init(int k, int l, int r) {
if(l > r) return;
if(l == r) v[k] = a[l];
else {
int m = (l+r)/2;
init(2*k,l,m); init(2*k+1,m+1,r);
}
}
int prod(int k, int l, int r, int p) {
if(l == r) return v[k];
int m = (r+l)/2, c = v[k];
if(p <= m) c += prod(2*k,l,m,p);
else c += prod(2*k+1,m+1,r,p);
return c;
}
void upd(int k, int x, int y, int l, int r, int z) {
if(l > r) return;
if(l == x && y == r) {v[k] += z; return;}
int m = (x+y)/2;
upd(2*k,x,m,l,min(m,r),z),upd(2*k+1,m+1,y,max(l,m+1),r,z);
}
};
int count_swaps(vector<int> v) {
int n = v.size();
segtree<0> t; vector<int> w(n); for(int i=0;i<n;i++) w[i] = i;
t.resz(n,w); t.init(1,0,n-1);
map<int,queue<int>> m;
int ans = 0;
for(int i=0;i<n;i++) {
if(m[-v[i]].empty()) m[v[i]].push(i);
else {
ans += t.prod(1,0,n-1,i)-t.prod(1,0,n-1,m[-v[i]].front())-(v[i]>0);
t.upd(1,0,n-1,m[-v[i]].front()+1,i-1,1);
m[-v[i]].pop();
}
}
return ans;
}
