#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
vector<int> solve(std::vector<int> A){
    int N=(int)A.size();
    if(N<=25){
        vector<int> res;
        for(int i=N-1;i>=0;i--)
            res.push_back(i);
        return res;
    }
    else{
        vector<int>resM, resD, cop=A;
        int i=0, j=0;
        unordered_map<int, vector<int>> pos;
        unordered_map<int, int> mp;
        for(int k=0;k<N;k++)
            pos[A[k]].push_back(k);
        sort(A.begin(), A.end());
        for(auto it:A)
            mp[it]++;
        int k=0;
        while(i<N){
                int init=mp[A[i]];
                k=1;
                for(auto it:pos[A[i]]){
                    if(k<=init/2)
                        resD.push_back(it);
                    else
                        resM.push_back(it);
                    k++;
                }
            i+=init;
        }
        for(auto it:resM)
            resD.push_back(it);
        return resD;
    }
}
