#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};
    sort(v.begin(), v.end());

    S = 0;
    for(int i = 0; i < n; i++) S += v[i].first;

    ll sp[n + 1];
    sp[0] = 0;
    for(int i = 0; i < n; i++) sp[i + 1] = sp[i] + v[i].first;

    int len = n / 2 - 1;
    ll suma = 0, cnt = 0;
    vector<int> poz;
    vector<int> alt;
    for(int i = n - 2; i >= 0; i--){
        if(cnt == len){
            alt.push_back(v[i].second);
            continue;
        }
        suma += v[i].first;
        cnt++;
        //cout << "i = " << i << " suma = " << suma << "\n";
        if(suma * 2 >= S){ suma -= v[i].first; cnt--; alt.push_back(v[i].second); }
        else if((suma + sp[len - cnt]) * 2 >= S){ suma -= v[i].first; cnt--; alt.push_back(v[i].second); }
        else poz.push_back(v[i].second);
    }

    poz.push_back(v[n - 1].second);
    for(int i = 0; i < alt.size(); i++) poz.push_back(alt[i]);

    return poz;
}
