#include "partition.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>

struct Element
{
    int val;
    int idx;
};

std::vector<Element> a;
std::vector<int> perm;
std::vector<int> permL;
std::vector<int> permR;
std::map<int, int> freq;

std::vector<int> solve(std::vector<int> A)
{
    for(int i = 0 ; i < A.size() ; ++i)
    {
        freq[A[i]] += 1;
    }

    for(int i = 0 ; i < A.size() ; ++i)
    {
        a.push_back({A[i], i});
    }

    std::sort(a.begin(), a.end(), [&](const Element &left, const Element &right)
    {
        return left.val < right.val;
    });

    for(int i = 0 ; i < a.size() ; )
    {
        int start = i;
        int end = i + freq[a[i].val] - 1;
        int mid = start + end >> 1;

        for(int ptr = start ; ptr <= mid ; ++ptr)
        {
            permL.push_back(a[ptr].idx);
        }

        for(int ptr = mid + 1 ; ptr <= end ; ++ptr)
        {
            permR.push_back(a[ptr].idx);
        }

        i = end + 1;
    }

    for(int x : permL)
    {
        perm.push_back(x);
    }

    for(int x : permR)
    {
        perm.push_back(x);
    }

    return perm;
}
