#include <bits/stdc++.h>
#define forint(i, N) for (int i = 0; i <(N); i++)
using namespace std;
typedef long long ll;
vector<int> tree(1000000, 0);
vector< queue<pair<int, int> > > v;
vector<int> target;
void build(int node, int a, int x, int y) {
if (y <= a) {
//cerr << a << " - " << x << " -- " << y << endl;
tree[node]++;
return;
}
//tree[node]++;
//cerr << a << " ja " << x << " - " << y << endl;
build(node * 2 + 1, a, x, (x + y) / 2);
if ((x + y) / 2 + 1 <= a) {
build(node * 2 + 2, a, (x + y) / 2 + 1, y);
}
}
ll count(int node, int a, int x, int y) {
if (x == y) {
//cerr << " ja " << tree[node] << endl;
return tree[node];
}
if (a <= (x + y) / 2) {
return tree[node] + count(node * 2 + 1, a, x, (x + y) / 2);
}
if (a >= (x + y) / 2 + 1) {
return tree[node] + count(node * 2 + 2, a, (x + y) / 2 + 1, y);
}
}
ll count_swaps(vector<int> s) {
v.resize(s.size() / 2 + 1);
target.resize(s.size(), -1);
forint(i, s.size()) {
if (v[abs(s[i])].empty() || v[abs(s[i])].front().first == s[i]) {
v[abs(s[i])].push({s[i], i});
}
else {
target[v[abs(s[i])].front().second] = i;
v[abs(s[i])].pop();
}
}
ll ans = 0;
forint(i, s.size()) {
if (target[i] == -1) {
continue;
}
ans = ans + target[i] + count(0, target[i], 0, s.size() - 1) - i - count(0, i, 0, s.size() - 1);
//cerr << "ja" << endl;
if (s[i] < 0) {
ans--;
}
//cerr << count(0, target[i], 0, s.size() - 1) << endl;
build(0, target[i] - 1, 0, s.size() - 1);
}
return ans;
}
