#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vint vector<int>
#define vll vector<long long>
#define fo(a, b, c) for (int a = b; a < (int)c; a++)
#define rfo(a, b, c) for (int a = b - 1; a >= (int)c; a--)
#define print(x) cout << x << "\n"
ll s2(vint s)
{
ll count = 0;
ll on, l, r;
while (s.size() > 0)
{
on = s[s.size() - 1];
l = s.size() - 1, r = s.size() - 1;
rfo(i, s.size() - 1, 0)
{
if (-s[i] == on)
{
if (s[i] > 0) // right
{
r = i;
}
else
{
l = i;
}
break;
}
}
if (r < l)
{ // right must be moved
count += (ll)s.size() - 1 - r;
s.erase(s.begin() + l);
s.erase(s.begin() + r);
}
else
{
count += (ll)s.size() - 2 - l;
s.erase(s.begin() + r);
s.erase(s.begin() + l);
}
}
return count;
}
ll s3(vint s)
{
int leftOn = 0;
int rightOn = 1;
ll sum = 0;
fo(i, 0, s.size())
{
if (s[i] > 0) //right
{
sum += abs(i - rightOn);
rightOn += 2;
}
else
{
sum += abs(i - leftOn);
leftOn += 2;
}
}
return sum / 2;
}
ll s4(vint s)
{
ll n = (ll)s.size() / 2;
return (n * n - n) / 2;
}
// s - the array of shoes, with -1 being left and 1 being right
ll count_swaps(vint s)
{
if (s.size() == 2)
return s[0] > 0 ? 1 : 0;
int val = abs(s[0]);
bool allSame = true;
int n = s.size() / 2;
bool halfed = true;
fo(i, 0, n)
{
if (s[i] > 0 || s[i + n] < 0 || (s[i] + s[i + n] != 0))
{
halfed = false;
}
if (abs(s[i]) != val || abs(s[i + n]) != val)
{
allSame = false;
}
// if(!allSame && !halfed) break;
}
if (allSame)
{
// print("s3");
return s3(s);
}
if (halfed)
{
// print("s4");
return s4(s);
}
// print("other");
return s2(s);
}
