#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ll long long
const int N = 2e5 + 10;
int was[N], t[4 * N], w[4 * N];
vector<int> pos[2 * N];
void push(int u){
w[2 * u + 1] += w[u];
w[2 * u + 2] += w[u];
t[2 * u + 1] += w[u];
t[2 * u + 2] += w[u];
w[u] = 0;
}
void upd(int u, int tl, int tr, int l, int r, int val){
if(l <= tl && tr <= r){
t[u] += val;
w[u] += val;
return;
}
push(u);
int tm = (tl + tr) / 2;
if(l <= tm)
upd(2 * u + 1, tl, tm, l, r, val);
if(r >= tm + 1)
upd(2 * u + 2, tm + 1, tr, l, r, val);
}
int get_pos(int u, int tl, int tr, int pos){
if(tl == tr)
return t[u] + tl;
push(u);
int tm = (tl + tr) / 2;
if(pos <= tm)
return get_pos(2 * u + 1, tl, tm, pos);
else
return get_pos(2 * u + 2, tm + 1, tr, pos);
}
long long count_swaps(vector<int> s) {
int n = s.size();
ll ans = 0;
for(int i = n - 1; i >= 0; --i)
pos[N + s[i]].pb(i);
for(int i = 0; i < n; ++i){
if(was[i])
continue;
pos[N + s[i]].pop_back();
if(s[i] < 0){
int p = pos[N + -1 * s[i]].back();
pos[N + -1 * s[i]].pop_back();
was[p] = 1;
ans += get_pos(0, 0, n, p) - get_pos(0, 0, n, i) - 1;
upd(0, 0, n, i + 1, p - 1, 1);
}else{
int p = pos[N + -1 * s[i]].back();
pos[N + -1 * s[i]].pop_back();
was[p] = 1;
ans += get_pos(0, 0, n, p) - get_pos(0, 0, n, i);
upd(0, 0, n, i, p - 1, 1);
}
// cout << i << " " << ans << endl;
}
return ans;
}
