// https://oj.uz/problem/view/IOI19_shoes
#include <bits/stdc++.h>
using namespace std;
pair<vector<int>, long long> bubbleSortSwaps(vector<int> a,int l, int r)
{
// alter merge sort to simulate bubble sort
if (l==r) // base case - single item covered
{
return {{a[l]},0};
}
int mid = (l+r)/2;
pair<vector<int>, long long> left = bubbleSortSwaps(a,l,mid);
pair<vector<int>, long long> right = bubbleSortSwaps(a,mid+1,r);
long long inv = left.second + right.second;
vector<int> merged;
int i = 0; // right pointer
int j = 0; // left pointer
while (j < left.first.size() && i < right.first.size())
{
// take element from left
if (right.first[i] >= left.first[j])
{
merged.push_back(left.first[j]);
j++;
}
// take element from right.
else{
merged.push_back(right.first[i]);
i++;
inv += (left.first.size()-j);
}
}
// left pointer exceeds boundary so we add all right
while (i < right.first.size())
{
merged.push_back(right.first[i]);
i++;
}
while (j < left.first.size())
{
merged.push_back(left.first[j]);
j++;
}
return {merged, inv};
}
void removeDuplicates(vector<int> &a, unordered_map<int,vector<int>> &index, int maxValue)
{
vector<int> pointers(maxValue+1,0);
for (int i = 0; i < a.size(); i++)
{
if (index.find(a[i])==index.end())
{
continue; // we've already modified this item, so skip it.
}
int p = pointers[abs(a[i])];
if (index[a[i]].size() - p > 1) // duplicates are present for this value.
{
pointers[abs(a[i])]++;
if (a[i] > 0)
{
a[index[0-a[i]][p]] = (0-(maxValue+1));
a[i] = maxValue+1;
}
else{
a[index[0-a[i]][p]] = maxValue+1;
a[i] = (0-(maxValue+1));
}
maxValue++;
}
}
}
long long count_swaps(vector<int> s)
{
unordered_map<int,vector<int>> index; // array of index occurrences
// for o(1) finding of left-right pairs
int maxValue = INT_MIN;
for (int i = 0; i < s.size(); i++)
{
if (s[i] > maxValue)
{
maxValue = s[i];
}
if (index.find(s[i])==index.end())
{
index[s[i]] = {i};
}
else{
index[s[i]].push_back(i);
}
}
removeDuplicates(s,index,maxValue);
vector<int> sorting(s.size(), -1); // blank arr
unordered_map<int,int> indexNew;
for (int i = 0; i < s.size(); i++)
{
indexNew[s[i]] = i;
}
int nextLeft = 0;
for (int i = 0; i < s.size(); i++)
{
if (sorting[i] != -1)
{
continue; // skip already chosen vals
}
if (s[i] > 0) // right shoe.
{
sorting[i] = nextLeft+1;
sorting[indexNew[0-s[i]]] = nextLeft;
}
else{ // left shoe
sorting[i] = nextLeft;
sorting[indexNew[0-s[i]]] = nextLeft+1;
}
nextLeft+=2;
}
return bubbleSortSwaps(sorting, 0, sorting.size()-1).second;
}
