# 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<ll> 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();
        if(sz != 1)
        {
            ll current = 0;
            deque<int> dq;

            int half = sz / 2 + sz % 2;
            for(int i = 0; i < half; i++)
            {
                current += a[b[i]];
                dq.push_back(i);
            }

            while(2 * current <= sum)
            {
                int top = dq.back();
                int bc = dq.front();
                dq.pop_front();
                bool flag = false;
                for(int i = top + 1; i < sz; i++)
                {
                    if(current - a[bc] + a[b[i]] >= sum / 2)
                    {
                        dq.push_back(i);
                        flag = true;
                        break;
                    }
                }

                if(flag) break;
                current += (a[b[sz - 1]] - a[bc]);
                dq.push_back(sz - 1);
            }

            for(auto& i : dq)
            {
                visited[b[i]] = true;
                answer.push_back(b[i]);
            }
        }
        else
        {
            visited[b[0]] = true;
            answer.push_back(b[0]);
        }
    }

    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;
}
