#include <bits/stdc++.h>
using namespace std;
#define ll long long
void update(int node, int left, int right, int point, vector<int> &tree)
{
if (left == right)
tree[node] = 1;
else
{
int m = (left + right) / 2;
if (point <= m)
update(2*node, left, m, point, tree);
else
update(2*node + 1, m + 1, right, point , tree);
tree[node] = tree[2*node] + tree[2*node + 1];
}
}
int querry(int node, int l, int r, int ql, int qr, vector<int> &tree)
{
if (ql <= l && r <= qr)
return tree[node];
int m = (l + r) / 2;
if (qr <= m)
return querry(2 * node, l, m, ql, qr, tree);
if (ql > m)
return querry(2 * node + 1, m + 1, r, ql, qr, tree);
return querry(2 * node, l, m, ql, qr, tree) + querry(2 * node + 1, m + 1, r, ql, qr, tree);
}
ll count_swaps (vector<int> S)
{
int n = S.size() / 2;
ll ans = 0;
vector<int> Taken(2 * n, 0);
vector<int> Tree(8 * n, 0);
vector<vector<int>> Poz(2 * n + 2);
vector<int> l(2*n + 2, 0);
for (int i = 0; i < 2 * n; i++)
{
if (S[i] < 0)
Poz[abs(S[i])].push_back(i);
else
Poz[S[i] + n].push_back(i);
}
for (int i = 0; i < 2 * n - 1; i++)
{
if (Taken[i] == 1)
continue;
if (S[i] < 0 && 0 - S[i + 1] == S[i])
{
Taken[i] = 1; Taken[i + 1] = 1;
l[abs(S[i])]++;
l[abs(S[i]) + n]++;
continue;
}
Taken[i] = 1;
int need;
if (S[i] < 0)
{
need = Poz[abs(S[i]) + n][l[abs(S[i]) + n]];
ans += need - i - 1 - querry(1, 0, 2*n-1, i + 1, need, Tree);
Taken[need] = 1;
update(1, 0, 2*n - 1, need, Tree);
}
else
{
need = Poz[abs(S[i])][l[abs(S[i])]];
ans += need - i - querry(1, 0, 2*n-1, i + 1, need, Tree);
Taken[need] = 1;
update(1, 0, 2*n-1, need, Tree);
}
l[abs(S[i]) + n]++;
l[abs(S[i])]++;
}
return ans;
}
