#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll a[401010];
ll t[1601010];
ll tAdd[1601010];
void build(ll v, ll vl, ll vr) {
if (vl == vr) {
t[v] = vl;
return;
}
ll vm = (vl + vr) / 2;
build(2 * v, vl, vm);
build(2 * v + 1, vm + 1, vr);
}
void push(ll v, ll vl, ll vr) {
if (tAdd[v] == 0)return;
if (vl == vr)t[v] += tAdd[v];
else {
tAdd[2 * v] += tAdd[v];
tAdd[2 * v + 1] += tAdd[v];
}
tAdd[v] = 0;
}
void upd(ll v, ll vl, ll vr, ll l, ll r, ll val) {
push(v, vl, vr);
if (l <= vl && vr <= r) {
tAdd[v] += val;
push(v, vl, vr);
return;
}
if (r < vl || vr < l)return;
ll vm = (vl + vr) / 2;
upd(2 * v, vl, vm, l, r, val);
upd(2 * v + 1, vm + 1, vr, l, r, val);
}
ll get(ll v, ll vl, ll vr, ll pos) {
push(v, vl, vr);
if (vl == vr)return t[v];
ll vm = (vl + vr) / 2;
if (pos <= vm)return get(2 * v, vl, vm, pos);
else return get(2 * v + 1, vm + 1, vr, pos);
}
vector<ll> g[401010];
ll poller[401010];
ll ans = 0;
bool used[401010];
ll ID[401010];
long long count_swaps(std::vector<int> s) {
n = s.size();
for (ll i = 1; i <= n; i++)
a[i] = s[i - 1];
build(1, 1, n);
for (ll i = 1; i <= n; i++)
g[a[i] + n + 1].push_back(i);
for (ll i = 1; i <= n; i++)ID[i] = i;
for (ll i = 1; i <= n; i++) {
if (used[i])continue;
if (a[i] < 0) {
ll Num = -a[i];
ll pos = g[Num + n + 1][poller[Num + n + 1]];
poller[Num + n + 1]++;
poller[a[i] + n + 1]++;
upd(1, 1, n, i + 1, pos - 1, 1);
ans += (get(1, 1, n, pos) - get(1, 1, n, i) - 1);
used[i] = true;
used[pos] = true;
continue;
}
if (a[i] > 0) {
ll Num = -a[i];
ll pos = g[Num + n + 1][poller[Num + n + 1]];
poller[Num + n + 1]++;
poller[a[i] + n + 1]++;
upd(1, 1, n, i + 1, pos, 1);
ans += (get(1, 1, n, pos) - get(1, 1, n, i) - 1);
used[i] = true;
used[pos] = true;
continue;
}
}
return ans;
}
