# include "partition.h"
# include <bits/stdc++.h>
# define ll long long
using namespace std;

vector<int> solve(vector<int> a)
{
    unordered_map<int, int> maskedValue;
    int mask = 0;
    vector<int> order;
    for(auto& value : a) order.push_back(value);
    sort(order.begin(), order.end());
    mask++;
    maskedValue[order[0]] = mask;
    for(int i = 1; i < (int)order.size(); i++)
    {
        if(order[i] != order[i - 1])
        {
            mask++;
            maskedValue[order[i]] = mask;
        }
    }

    vector<vector<int>> positions((int)a.size() + 1);

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

    vector<int> b;
    vector<int> answer;
    vector<bool> visited((int)a.size() + 1, false);

    for(int value = 1; value <= mask; value++)
    {
        for(int i = 0; i < (int)positions[value].size(); i++)
        {
            b.push_back(positions[value][i]);
        }
    }

    if(!b.empty())
    {
        int n = (int)b.size();
        int nHalf = (n + n % 2) / 2;

        for(int i = 0; i < (nHalf - nHalf % 2) / 2; i++)
        {
            visited[b[i]] = true;
            answer.push_back(b[i]);
        }

        for(int i = (n - (nHalf + nHalf % 2) / 2); i < n; i++)
        {
            visited[b[i]] = true;
            answer.push_back(b[i]);
        }
    }

    for(int i = 0; i < (int)a.size(); i++) if(!visited[i]) answer.push_back(i);
    return answer;
}
