#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2 * 1e6 ;
vector<vector<int>>g;
std::vector<int> solve(std::vector<int> a) {
    g.resize(nmax+1);
    for ( int i = 0 , n = a.size() ; i < n ; ++ i )g[a[i]].push_back(i);
    sort(a.begin(),a.end());
    vector<int>ans;
    int sum = 0 ;
    for ( auto it : a ) sum += it ;
    int n = a.size();
    int o = 0 ;
    o += 2 * a[n-1];
    ans.push_back(a[n-1]);
    int nr = 1 ;
    int i = 0 ;
    for ( i = 0 ; i < n - 1 && o < sum ; ++ i , ++ nr ){
    o += 2 * a[i] ;
    ans.push_back(a[i]);
    }
    int mij = n / 2 ;
    if ( nr < mij ) {
    for ( ; nr < mij ; ++ nr , ++ i ) ans.push_back(a[i]);
    }
    reverse(ans.begin(),a.end());
    vector<bool>fr(n+1,0);
    vector<int>r;
    for ( auto it : ans ) {
    r.push_back(g[it][g[it].size()-1]) ;
    fr[g[it][g[it].size()-1]]=1;
    g[it].pop_back();
    }
    i = 0 ;
    for ( i = 0 ; i < n ; ++ i ) if ( !fr[i] ) r.push_back(i);
    return r ;
}

