#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
{
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
}
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;
// }
