#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector <int> res1;
vector <int> res2;
std::vector<int> solve(std::vector<int> A)
{
    vector <pair<int,int>> b;
    for (int i = 0; i < A.size();i++)
    {
        b.push_back({A[i], i});
    }
    sort(b.begin(), b.end());
    /*for (int i = 0; i < A.size(); i++)
    {
        cout << b[i].first << " ";
    }
    cout << endl;*/
    for (int i = 0; i < A.size();)
    {
        int curr = b[i].first;
        int i0 = i;
        //cout << curr << " " << i0 << " ";
        while (b[i].first == curr)
        {
            i++;
        }
        //cout << curr << " " << i << " " << endl;
        for (int j = i0; j < i0+(i-i0)/2; j++)
            res1.push_back(b[j].second);
        for (int j = i0+(i-i0)/2; j < i; j++)
            res2.push_back(b[j].second);
    }
    for (int i = 0; i < res2.size(); i++)
        res1.push_back(res2[i]);
    return {res1};
}
