#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t[800000] = {0};
void update(int v, int tl, int tr, int idx, int val)
{
if (tl == tr)
{
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (idx <= tm)
update(v*2, tl, tm, idx, val);
else
update(v*2+1, tm+1, tr, idx, val);
t[v] = t[v*2] + t[v*2+1];
}
int sum(int v, int tl, int tr, int l, int r)
{
if (r < l || tr < tl)
return 0;
if (tl == l && tr == r)
return t[v];
int tm = (tl + tr) / 2;
return sum(v*2, tl, tm, l, min(r, tm))
+ sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}
long long count_swaps(vector<int> s)
{
int n = s.size() / 2;
if (n == 1)
return s[1] < s[0];
vector<pair<int,int>> neg, pos;
for (int i = 0; i < 2 * n; i++)
if (s[i] < 0)
neg.push_back({-s[i],i});
else
pos.push_back({s[i],i});
sort(neg.begin(), neg.end());
sort(pos.begin(), pos.end());
vector<pair<int,int>> pairs(n);
for (int i = 0; i < n; i++)
pairs[i] = {neg[i].second, pos[i].second};
sort(pairs.begin(), pairs.end(), [](const pair<int,int> &a, const pair<int,int> &b)
{return min(a.first,a.second) < min(b.first,b.second);});
ll res = 0;
for (auto [i, j] : pairs)
{
if (i < j)
{
// j must move to the right of i.
res += j - i - 1 - sum(1, 0, 2*n-1, i+1, j-1);
update(1, 0, 2*n-1, j, 1);
}
else
{
// i must move to the left of j.
res += i - j - sum(1, 0, 2*n-1, j+1, i-1);
update(1, 0, 2*n-1, i, 1);
}
}
return res;
}
