#include<bits/stdc++.h>
#include "partition.h"

using namespace std;
using ll = long long;

vector< pair<ll, int> > A;
ll S = 0;
int n;
vector<int> eu, sol;
int mini = 0;

void bkt(int it, ll suma){
    //cerr << "pot fi la " << it << " " << suma << '\n';
    if(suma * 2LL >= S){
        if( abs((int)eu.size() - (n - (int)eu.size())) < mini){
            mini = abs((int)eu.size() - (n - (int)eu.size()));
            sol = eu;
        }
        return;
    }
    if(it == n) return;

    bkt(it + 1, suma);

    eu.push_back(A[it].second);
    bkt(it + 1, suma + A[it].first);
    eu.pop_back();
}

vector<int> solve(vector<int> a){
    n = a.size();

    if(n == 1) return {0};

    vector< pair<ll, int> > v;
    v.resize(n);
    for(int i = 0; i < n; i++){
        v[i] = {a[i], i};
        S += v[i].first;
    }
    sort(v.begin(), v.end());

    int len = n / 2;
    for(int pref = 0; pref <= len; pref++){
        int suma = 0;
        for(int i = 0; i < pref; i++) suma += v[i].first;
        bool bun = 1;
        for(int j = n - ( len - pref ); j < n; j++){
            suma += v[j].first;
            if(suma * 2LL > S && j != n - 1) bun = 0;
        }

        if(bun){
            vector<int> sol;
            for(int i = 0; i < pref; i++) sol.push_back(v[i].second);
            for(int j = n - ( len - pref ); j < n; j++) sol.push_back(v[j].second);
            for(int i = pref + 1; i < n - (len - pref); i++) sol.push_back(v[i].second);
            return sol;
        }
    }
}