#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast \
ios_base::sync_with_stdio (false); \
cin.tie (NULL); \
cout.tie (NULL)
using namespace std;
ll _mergeSort(ll arr[], ll temp[],
ll left, ll right);
ll merge(ll arr[], ll temp[],
ll left, ll mid, ll right);
/* This function sorts the input
array and returns the number
of inversions in the array */
ll mergeSort(ll arr[], ll array_size)
{
ll temp[array_size];
return _mergeSort(arr, temp, 0,
array_size - 1);
}
/* An auxiliary recursive function that
sorts the input array and returns the
number of inversions in the array. */
ll _mergeSort(ll arr[], ll temp[],
ll left, ll right)
{
ll mid, inv_count = 0;
if (right > left)
{
/* Divide the array llo two parts and
call _mergeSortAndCountInv() for
each of the parts */
mid = (right + left) / 2;
/* Inversion count will be sum of inversions
in left-part, right-part and number of
inversions in merging */
inv_count += _mergeSort(arr, temp,
left, mid);
inv_count += _mergeSort(arr, temp,
mid + 1, right);
// Merge the two parts
inv_count += merge(arr, temp,
left, mid + 1, right);
}
return inv_count;
}
/* This funt merges two sorted arrays and
returns inversion count in the arrays.*/
ll merge(ll arr[], ll temp[],
ll left, ll mid, ll right)
{
ll i, j, k;
ll inv_count = 0;
// i is index for left subarray
i = left;
// j is index for right subarray
j = mid;
// k is index for resultant merged
// subarray
k = left;
while ((i <= mid - 1) &&
(j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
/* This is tricky -- see above
explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left
subarray (if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right
subarray (if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/* Copy back the merged elements to
original array*/
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
ll count_swaps(vector <int> shoes)
{
ll n=sz(shoes)/2;
map <int,vector<int>> idx;
map <int,int> loc;
vector <bool> marked(2*n);
rep(i,0,2*n-1)
idx[shoes[i]].pb(i);
ll arr[2*n];
rep(i,0,2*n-1)
if(!marked[i])
{
ll a=shoes[i];
ll b=-shoes[i];
ll i1=i;
ll i2=idx[b][loc[b]];
loc[a]++;
loc[b]++;
marked[i1]=marked[i2]=true;
if(a<0)
arr[i1]=2*i+1, arr[i2]=2*i+2;
else
arr[i1]=2*i+2, arr[i2]=2*i+1;
}
return mergeSort(arr,2*n);
}
// signed main()
// {
// fast;
// // freopen("milkorder.in","r",stdin);
// // freopen("milkorder.out","w",stdout);
// cout<<count_swaps({-2 ,3 ,-4 ,-3 ,-2 ,2 ,4 ,2});
// return 0;
// }
