#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<long long> cnt(MAXN, 0), ST(4*MAXN, 0);
void update(int v, int l, int r, int k, int x){
if(l == r){
ST[v] += x;
return;
}
int m = (l + r)/2;
if(k <= m){
update(2*v, l, m, k, x);
}
else{
update(2*v + 1, m + 1, r, k, x);
}
ST[v] = ST[2*v] + ST[2*v + 1];
return;
}
long long sum(int v, int l, int r, int a, int b){
if(l > b or r < a) return 0;
if(l >= a and r <= b) return ST[v];
int m = (l + r)/2;
return sum(2*v, l, m, a, b) + sum(2*v + 1, m + 1, r, a, b);
}
long long count_swaps(vector<int> S){
map<int, deque<int>> m;
int N = S.size();
long long ans = 0;
for(int i = 0; i < N; i++){
if(S[i] > 0 and m[-S[i]].size() > 0){
int j = m[-S[i]].front();
ans += i - j - 1 + sum(1, 0, N - 1, j, i);
update(1, 0, N - 1, i, -1);
update(1, 0, N - 1, j, 1);
m[-S[i]].pop_front();
}
else if(S[i] < 0 and m[-S[i]].size() > 0){
int j = m[-S[i]].front();
ans += i - j + sum(1, 0, N - 1, j, i);
update(1, 0, N - 1, i, -1);
update(1, 0, N - 1, j, 1);
m[-S[i]].pop_front();
}
else{
m[S[i]].push_back(i);
}
}
return ans;
}
