#include "partition.h"
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> solve(vector<int> a) {
    int n = a.size();
    if(n == 1) {
        return {0};
    }

    vector<int> idx(n);
    for(int i = 0; i < n; i++) {
        idx[i] = i;
    }
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return a[x] > a[y];
    });
    long long sum = 0;
    for(int i = 0; i < n; i++) {
        sum += a[i];
    }

    vector<int> new_idx, pref, suff;
    pref.reserve(n);
    suff.reserve(n);
    for(int i = 0; i < n; i++) {
        int j = i;
        while(j < n && a[idx[i]] == a[idx[j]]) {
            j++;
        }
        for(int q = i; q + 1 < j; q += 2) {
            pref.push_back(idx[q]);
            suff.push_back(idx[q + 1]);
        }
        if((j - i) % 2 == 1) {
            new_idx.push_back(idx[j - 1]);
        }
        i = j - 1;
    }
    idx = new_idx;
    n = idx.size();

    vector<int> mari, mici;
    mari.reserve(n);
    mici.reserve(n);
    long long aux = 0;
    for(int i = 0; i < n; i++) {
        if(aux <= sum / 2) {
            aux += a[idx[i]];
            mari.push_back(idx[i]);
        } else {
            mici.push_back(idx[i]);
        }
    }

    vector<int> umple, rest;
    umple.reserve(n);
    while(!mici.empty() && (int)mari.size() + (int)umple.size() <= (n - 1) / 2) {
        if(aux + a[mici.back()] - a[mari.back()] > sum / 2) {
            aux -= a[mari.back()];
            rest.push_back(mari.back());
            mari.pop_back();
        }
        umple.push_back(mici.back());
        aux += a[mici.back()];
        mici.pop_back();
    }

    vector<int> answer;
    for(auto it : pref) {
        answer.push_back(it);
    }
    for(auto it : umple) {
        answer.push_back(it);
    }
    for(auto it : mari) {
        answer.push_back(it);
    }
    for(auto it : mici) {
        answer.push_back(it);
    }
    for(auto it : rest) {
        answer.push_back(it);
    }
    for(auto it : suff) {
        answer.push_back(it);
    }

    return answer;
}
