#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
int N,Left,Right,V;
long long seg[1 << 18];
long long Query(int l = 1, int r = N, int ind = 1){
if(l > Right or r < Left) return 0;
if(l >= Left && r <= Right) {
return seg[ind];
}
int mid = (l + r) / 2;
return Query(l, mid, ind * 2) + Query(mid + 1, r, ind * 2 + 1);
}
void Update(int Pos, int V){
int ind = N + Pos - 1;
seg[ind] += V;
while(ind /= 2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
}
long long count_swaps(vector<int>s) {
int n = s.size(); long long ans = 0;
map<int,set<int>>d;
N = exp2(ceil(log2(n)));
for(int i = 0; i < n; i++) Update(i + 1, 1);
for(int i = 0; i < n; i++){
int f = -1;
if(d[-s[i]].size()){
f = *d[-s[i]].begin();
}
if(f != -1){
Left = 1; Right = f + 1;
int x = Query(), y = 0;
Right = i + 1;
y = Query();
ans += (y - x);
if(s[i] > 0) ans--;
Update(f + 2, 1);
Update(i + 1, -1);
d[-s[i]].erase(f);
}else{
d[s[i]].insert(i);
}
}
return ans;
}
