#include "shoes.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define ll long long
using namespace std;
struct segTree
{
vector<int> nodes;
vector<int> lazy;
segTree(int s) : nodes(s * 4) {}
void update(int n, int tl, int tr, int l, int r, int val) {
if (l <= tl && tr <= r) {
nodes[n] += val;
return;
}
int tm = (tl + tr) / 2;
if (l <= tm) update(n * 2, tl, tm, l, r, val);
if (tm + 1 <= r) update(n * 2 + 1, tm + 1, tr, l, r, val);
}
int query(int n, int tl, int tr, int pos) {
int res = nodes[n];
if (tl == tr) return res;
int tm = (tl + tr) / 2;
if (pos <= tm) res += query(n * 2, tl, tm, pos);
else res += query(n * 2 + 1, tm + 1, tr, pos);
return res;
}
};
ll count_swaps(vector<int> s) {
int DN = s.size();
segTree tree(DN);
for (int i = 1; i <= DN; ++i) {
tree.update(1, 1, DN, i, i, i);
}
ll tot = 0;
set<ii> ops;
map<int, queue<int>> pq;
for (int i = 0; i < DN; ++i) {
int a = s[i];
if (pq[-a].size()) {
int b = pq[-a].front();
pq[-a].pop();
ops.insert({b, i});
if (a < 0) tot++;
// cerr << "P " << b << " " << i << endl;
}
else pq[a].push(i);
}
for (auto a : ops) {
int p1 = tree.query(1, 1, DN, a.first + 1);
int p2 = tree.query(1, 1, DN, a.second + 1);
tot += p2 - p1 - 1;
tree.update(1, 1, DN, a.first + 1, DN, -1);
tree.update(1, 1, DN, a.second + 1, DN, -1);
}
return tot;
}
