#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;
vector<int> sumRight(2 * n + 1);
for (int i = 1; i <= 2 * n; i++)
{
if (s[i - 1] > 0)sumRight[i]++;
sumRight[i] += sumRight[i - 1];
}
for (int i = 0; i < 2 * n; i++)
{
if (s[i] < 0)
{
if (match[i] > i)
{
res += sumRight[match[i]] - sumRight[i];
} else
{
res += sumRight[i] - sumRight[match[i]];
}
}
}
vector<array<int,2 >> rivals;
vector<array<int, 2>> livals;
for (int i = 0; i < 2 * n; i++)
{
if (s[i] < 0)
{
if (match[i] > i) rivals.push_back({i, match[i]});
else livals.push_back({match[i], i});
}
}
for (auto c1 : rivals)
{
for (auto c2 : livals)
{
if (!(livals[1] < rivals[0] || livals[0] > rivals[1])) res++;
}
}
for (int i = 0; i < 4 * N; i++) tree[i] = 0;
for (int i = 0; i < 2 * n; i++)
{
if (s[i] < 0 && match[i] > i)
{
res += getSum(match[i], N - 1, 0, N - 1, 1);
ins(1, match[i], 0, N - 1, 1);
}
}
for (int i = 0; i < 4 * N; i++) tree[i] = 0;
for (int i = 2 * n - 1; i >= 0; i--)
{
if (s[i] < 0 && match[i] < i)
{
res += getSum(0, match[i], 0, N - 1, 1);
ins(1, match[i], 0, N - 1, 1);
}
}
return res;
}
/*
3
3 2 -3 3 -2 -3
*/
