#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define inf 1000000000
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int n, bit[200005], negpointer[100005], pospointer[100005];
vi neg[100005], pos[100005];
bool used[200005];
void update(int x, int upd) {
for (int i = x; i <= n; i += (i & (-i))) {
bit[i] += upd;
}
}
int query(int x) {
int ret = 0;
for (int i = x; i > 0; i -= (i & (-i))) {
ret += bit[i];
}
return ret;
}
long long count_swaps(vector<int> a) {
n = a.size();
FOR(i, 1, n) {
update(i, 1);
if (a[i-1] > 0) {
pos[a[i-1]].pb(i);
} else {
neg[-a[i-1]].pb(i);
}
}
ll ans = 0;
FOR(i, 1, n) {
if (used[i]) continue;
if (a[i-1] < 0) {
update(i, -1);
ans += query(pos[-a[i-1]][pospointer[-a[i-1]]] - 1);
update(pos[-a[i-1]][pospointer[-a[i-1]]], -1);
used[pos[-a[i-1]][pospointer[-a[i-1]]]] = true;
pospointer[-a[i-1]]++;
negpointer[-a[i-1]]++;
} else {
update(i, -1);
//cout << neg[a[i-1]][negpointer[a[i-1]]] << endl;
ans += query(neg[a[i-1]][negpointer[a[i-1]]] - 1) + 1;
update(neg[a[i-1]][negpointer[a[i-1]]], -1);
used[neg[a[i-1]][negpointer[a[i-1]]]] = true;
pospointer[a[i-1]]++;
negpointer[a[i-1]]++;
}
//cout << i << ' ' << ans << endl;
}
return ans;
}
