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

const int MAXN = 2 * 1e6 + 1;
int n;
unordered_map<int, vector<int>> key;
set<int> s;
bool visited[MAXN];

vector<int> solve(vector<int> a)
{
    vector<int> answer;
    n = (int)a.size();
    for(int i = 0; i < n; i++)
    {
        visited[i] = false;
        key[a[i]].push_back(i);
        s.insert(a[i]);
    }

    vector<int> b;
    ll sum = 0;

    for(auto& value : s)
    {
        int sz = (int)key[value].size();
        for(int i = 0; i < (sz - sz % 2) / 2; i++)
        {
            ///cout << value << " : " << key[value][i] << '\n';
            answer.push_back(key[value][i]);
            visited[key[value][i]] = true;
        }

        if(sz % 2 != 0)
        {
            b.push_back(key[value][sz - 1]);
            sum += a[key[value][sz - 1]];
        }
    }

    if(!b.empty())
    {
        int sz = (int)b.size();
        int nHalf = (sz + sz % 2) / 2;
        vector<int> answer;

        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 < n; i++) if(!visited[i]) answer.push_back(i);
    for(auto value : s)
    {
        key[value].clear();
    }
    s.clear();
    return answer;
}
