#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int N = 200005;
int tree[4 * N];
void ins(int num, int i, int a, int b, int node)
{
if (a == b)
{
tree[node] = num;
return;
}
int mid = (a + b) / 2;
if (i <= mid) ins(num, i, a, mid, node * 2);
if (i > mid) ins(num,i ,mid + 1, b, node * 2 + 1);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int getSum(int from, int to, int a, int b, int node)
{
if (from <= a && b <= to) return tree[node];
int mid = (a + b) / 2;
int res = 0;
if (from <= mid) res += getSum(from, to, a, mid, node * 2);
if (to > mid) res += getSum(from, to, mid + 1, b, node * 2+ 1);
return res;
}
long long count_swaps(std::vector<int> s) {
n = s.size() / 2;
vector<vector<int>> isAt(n + 1);
for (int i = 0; i < s.size(); i++)
{
if (s[i] < 0) isAt[abs(s[i])].push_back(i);
}
vector<int> match(s.size());
for (int i = s.size() - 1; i >= 0; i--)
{
if (s[i] > 0)
{
match[i] = isAt[s[i]].back();
match[isAt[s[i]].back()] = i;
isAt[s[i]].pop_back();
}
}
ll res = 0;
for (int i = 0; i < 2 * n; i++) ins(1, i, 0, N - 1, 1);
for (int i = 0; i < 2 * n; i++)
{
if (match[i] > i)
{
if (s[i] > 0)
{
res++;
}
res += getSum(i + 1, match[i] - 1, 0, N - 1, 1);
ins(0, i, 0, N - 1, 1);
ins(0, match[i], 0, N - 1, 1);
}
}
return res;
}
/*
5
1 2 -2 2 -2 -1 3 2 -3 -2
*/
