#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 + 1);
vector<int> l(2*n + 1, 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; i++)
{
if (Taken[i] == 1)
continue;
int p1 = Poz[abs(S[i])][l[abs(S[i])]];
int p2 = Poz[abs(S[i]) + n][l[abs(S[i]) + n]];
l[abs(S[i])]++;
l[abs(S[i]) + n]++;
if (p2 == p1 + 1)
continue;
if (p1 < p2)
ans += p2 - p1 - 1 - querry(1, 0, 2*n-1, p1, p2, Tree);
else
ans += p1 - p2 - querry(1, 0, 2*n-1, p2, p1, Tree);
update(1, 0, 2*n-1, p1, Tree);
update(1, 0, 2*n-1, p2, Tree);
Taken[p1] = 1; Taken[p2] = 1;
}
return ans;
}
