// 65 points
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int nt = 1;
vector<int> st;
int get_range(int l, int r, int k, int x, int y)
{
if (x > r || y < l) return 0;
if (x >= l && y <= r) return st[k];
int c = (x + y) / 2;
return get_range(l, r, k*2, x, c) + get_range(l, r, k*2|1, c+1, y);
}
ll count_swaps(vector<int> s)
{
// 1. Find pairs
// 2. Use segment tree to keep track of offsets
// 3. Profit
const ll N = s.size() / 2;
vector<queue<int>> vq(4 * N + 2);
// Finding mathcing shoes:)
vector<int> match(2 * N);
for (int i = 0; i < 2 * N; i++)
{
if (vq[2 * N + 1 - s[i]].size())
{
int matchIndex = vq[2 * N + 1 - s[i]].front();
match[i] = matchIndex;
match[matchIndex] = i;
vq[2 * N + 1 - s[i]].pop();
}
else
{
vq[2 * N + 1 + s[i]].push(i);
}
}
// Offset segment tree:)
while (nt < 2 * N)
nt <<= 1;
st = vector<int>(2*nt);
// Profit B)
ll res = 0;
int l = 0, r = 2*N - 1;
while (l < r)
{
while (match[l] == -1)
{
if (++l >= r)
return res;
}
int leftMatch = match[l];
int offset_l = get_range(0, l, 1, 0, nt - 1);
int offset_match = get_range(0, leftMatch, 1, 0, nt - 1);
int range = leftMatch + offset_match - (l + offset_l);
if (s[l] < 0) range--;
res += range;
match[l] = -1; match[leftMatch] = -1;
{
int i = nt + l;
st[i]++;
for (i /= 2; i >= 1; i /= 2)
st[i] = st[i * 2] + st[i * 2 | 1];
}
{
int i = nt + leftMatch;
st[i]--;
for (i /= 2; i >= 1; i /= 2)
st[i] = st[i * 2] + st[i * 2 | 1];
}
}
return res;
}
