#include <bits/stdc++.h>
#define mod 1000000007LL
#define inf 1e17
#define ll long long
using namespace std;
void printvec(vector<int> vec)
{
for (auto &&e : vec)
{
cout << e << ' ';
}
cout << endl;
}
ll maxn = 2e5 + 3;
vector<ll> tree(4*maxn);
ll query(ll node, ll x, ll y, ll l, ll r)
{
if(max(l,x) > min(r, y))
{
return 0;
}
if(x <= l && r <= y)
{
return tree[node];
}
ll mid = (l+r)/2;
return query(node*2, x, y, l, mid) + query(node*2+1,x, y, mid+1, r);
}
void update(ll node, ll l, ll r, ll index, ll val)
{
if(index < l || index > r)
{
return;
}
if(l == r)
{
tree[node] = val;
return;
}
ll mid = (l+r)/2;
update(node*2, l, mid, index, val);
update(node*2+1, mid+1, r, index, val);
tree[node] = tree[node*2] + tree[node*2 + 1];
}
ll count_swaps(vector<int> s)
{
ll n = s.size() / 2;
bool sametype = true;
for (int i = 1; i < n; i++)
{
if(abs(s[i])!=abs(s[i-1]))
{
sametype = false;
break;
}
}
if(n == 1) return s[0] > s[1];
else if(n <= 8)
{
ll ans = inf;
vector<pair<ll, ll>> perm;
for (int i = 0; i < 2 * n; i++)
{
if (s[i] > 0)
{
perm.push_back({-s[i], s[i]});
}
}
sort(perm.begin(), perm.end());
vector<int> temp = s;
do
{
s = temp;
ll subans = 0;
vector<int> v;
for (int i = 0; i < n; i++)
{
v.push_back(perm[i].first);
v.push_back(perm[i].second);
}
map<ll,vector<ll>> index;
for (int i = 0; i < 2*n; i++)
{
index[v[i]].push_back(i);
}
vector<pair<ll,ll>> arr;
for (int i = 0; i < 2*n; i++)
{
arr.push_back({s[i],index[s[i]][0]});
index[s[i]].erase(index[s[i]].begin());
}
for (int i = 1; i < 2*n; i++)
{
for (int j = 0; j < i; j++)
{
if(arr[j].second > arr[i].second)subans++;
}
}
ans = min(ans, subans);
} while (next_permutation(perm.begin(), perm.end()));
return ans;
}
else
{
ll ans = inf;
ll subans = 0;
vector<int> v;
for (int i = 0; i < 2*n; i++)
{
if(s[i] > 0)
{
v.push_back(-s[i]);
v.push_back(s[i]);
}
}
map<ll,set<ll>> index;
for (int i = 0; i < 2*n; i++)
{
index[v[i]].insert(i);
}
vector<int> arr;
for (int i = 0; i < 2*n; i++)
{
arr.push_back(*(index[s[i]].begin()));
index[s[i]].erase(index[s[i]].begin()); // here
}
// printvec(arr);
for (int i = 2*n-1; i >= 0; i--)
{
ll ac = query(1,0,arr[i],0,2*n-1);
subans += ac;
update(1,0,2*n-1,arr[i],1);
}
ans = min(ans, subans);
// } while (next_permutation(perm.begin(), perm.end()));
return ans;
}
}
// int main()
// {
// cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
// }
