#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
struct fenwick
{
int n;
vector<int> bit;
fenwick() {}
fenwick(int n)
{
this->n = n + 5;
bit.resize(n + 5);
}
void add(int pos, int val)
{
while (pos < n)
{
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos)
{
int ans = 0;
while (pos)
{
ans += bit[pos];
pos -= pos & -pos;
}
return ans;
}
int get(int l, int r)
{
return get(r) - get(l - 1);
}
int find(int k)
{
int sum = 0, pos = 0;
for (int i = __lg(n); i >= 0; i--)
{
if (pos + (1 << i) < n && sum + bit[pos + (1 << i)] < k)
{
sum += bit[pos + (1 << i)];
pos += (1 << i);
}
}
return pos + 1;
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size() / 2;
fenwick tree(2 * n);
vector<deque<int>> l(n + 1), r(n + 1);
for (int i = 0; i < 2 * n; i++)
{
if (s[i] < 0) l[-s[i]].push_back(i + 1);
else r[s[i]].push_back(i + 1);
}
vector<int> del(2 * n);
long long ans = 0;
for (int i = 1; i <= 2 * n; i++) tree.add(i, 1);
for (int i = 0; i < 2 * n; i++)
{
if (del[i])
{
continue;
}
if (s[i] < 0)
{
l[-s[i]].pop_front();
tree.add(i + 1, -1);
ans += tree.get(r[-s[i]][0] - 1);
tree.add(r[-s[i]][0], -1);
del[r[-s[i]][0] - 1] = 1;
r[-s[i]].pop_front();
}
else
{
r[s[i]].pop_front();
tree.add(i + 1, -1);
ans += tree.get(l[s[i]][0]);
tree.add(l[s[i]][0], -1);
del[l[s[i]][0] - 1] = 1;
l[s[i]].pop_front();
}
}
return ans;
}
// int main()
// {
// cout << count_swaps({2, 1, -1, -2});
// return 0;
// }
