#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define lch id << 1
#define rch id << 1 | 1
const int N = 1e5 + 5;
struct IT {
int n;
i64 tree[N << 2];
i64 lazy[N << 2];
void down(int id) {
if(lazy[id] == 0)
return;
tree[lch] += lazy[id];
lazy[lch] += lazy[id];
tree[rch] += lazy[id];
lazy[rch] += lazy[id];
lazy[id] = 0;
}
void build(int id, int l, int r) {
if(l == r) {
tree[id] = r;
return;
}
int m = l + r >> 1;
build(lch, l, m);
build(rch, m + 1, r);
tree[id] = max(tree[lch], tree[rch]);
}
void update(int id, int l, int r, int u, int v, int k) {
if(r<u or l>v)
return;
if(u <= l and r <= v) {
tree[id] += k;
lazy[id] += k;
return;
}
int m = l + r >> 1;
down(id);
update(lch, l, m, u, v, k);
update(rch, m + 1, r, u, v, k);
tree[id] = max(tree[lch], tree[rch]);
}
i64 get(int id, int l, int r, int pos) {
if(r<pos or l>pos)
return 0;
if(l == r)
return tree[id];
int m = l + r >> 1;
down(id);
return max(get(lch, l, m, pos), get(rch, m + 1, r, pos));
}
void create(int _n) {
n = _n;
build(1, 1, n);
}
void update(int l, int r, int k) {
return update(1, 1, n, l, r, k);
}
int get(int pos) {
return get(1, 1, n, pos);
}
} ST;
i64 count_swaps(vector<int> a) {
i64 ans = 0;
map<int, deque<int>> res;
int n = a.size();
ST.create(n);
for(int i = 0; i < n; i++) {
if(res[-a[i]].empty())
res[a[i]].emplace_back(i);
else {
int l = res[-a[i]].front() + 1;
res[-a[i]].pop_front();
int r = i+1;
ans += ST.get(r) - ST.get(l) - (a[i] > 0);
ST.update(l, r, 1);
}
}
return ans;
}
