#include <bits/stdc++.h>
#include "shoes.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
queue<int> q1[100005], q2[100005];
int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid,
int right);
/* This function sorts the
input array and returns the
number of inversions in the array */
int mergeSort(int arr[], int array_size)
{
int 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. */
int _mergeSort(int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left) {
/* Divide the array into 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.*/
int merge(int arr[], int temp[], int left, int mid,
int right)
{
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
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;
}
long long count_swaps(vector<int> s)
{
int n = s.size();
int cnt = -1;
for(int i = 0; i < n; i++)
{
if(s[i] < 0)
{
cnt+=2;
q1[-s[i]].push(cnt);
q2[-s[i]].push(cnt);
}
}
for(int i = 0; i < n; i++)
{
if(s[i] > 0)
{
int prev = s[i];
s[i] = q2[s[i]].front()+1;
q2[prev].pop();
}
else
{
int prev = s[i];
s[i] = q1[-s[i]].front();
q1[-prev].pop();
}
}
int k[n];
for(int i = 0; i < n; i++)
{
k[i] = s[i];
}
return mergeSort(k, n);
}
/*
int main()
{
int n;
cin >> n;
vint a(2*n);
for(int i = 0; i < 2*n; i++)
{
cin >> a[i];
}
cout << count_swaps(a);
}
*/
/*
5
-2 -1 1 2 -1 1 -2 -1 1 2
*/
