#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]];
}
}
}
for (int i = 0; i < 2 * n; i++)
{
for (int j = i + 1; j < 2 * n; j++)
{
if (s[i] < 0 && s[j] < 0)
{
array<int, 2> ival1 = {min(match[i], i), max(match[i], i)};
array<int, 2> ival2 = {min(match[j], j), max(match[j], j)};
if (ival1[0] >= ival2[0] && ival1[1] <= ival2[1])
{
res++;
continue;
}
if (ival2[0] >= ival1[0] && ival2[1] <= ival1[1])
{
res++;
continue;
}
int d1 = match[i] - i;
int d2 = match[j] - j;
if (d1 > 0 && d2 < 0 || d1 < 0 && d2 > 0)
{
if (!(ival1[1] < ival2[0] || ival1[0] > ival2[1]))
{
res++;
continue;
}
}
}
}
}
/*
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 (!(c2[1] < c1[0] || c2[0] > c1[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;
}
/*
5
1 2 -2 2 -2 -1 3 2 -3 -2
*/
