
#include <bits/stdc++.h>
#include "partition.h"
//#include "grader.cpp"
using namespace std;

typedef long long ll;

vector<int> solve(vector<int> a) {

    int n = a.size();
    ll sm = 0;
    for(int &i : a) sm += i;

    vector<int> b(n);
    iota(b.begin(), b.end(),0);

    sort(b.begin(), b.end(), [&](int x, int y) {
         return a[x] > a[y]; });

    vector<int> out;
    for(int r = 0; r < n; r += 2)
        out.push_back(b[r]);
    for(int r = n-1-(n&1); r >= 0; r -= 2)
        out.push_back(b[r]);

    ll smo = 0, cnt = 0;
    for(int &i : out) {
        smo += a[i];
        cnt ++ ;
        if(smo*2 >= sm)break;
    }
    cnt = abs(cnt - (n-cnt));

    auto out2 = out;
    reverse(out2.begin(), out2.end());

    smo = 0; ll cnt2 = 0;
    for(int &i : out2) {
        smo += a[i];
        cnt2 ++ ;
        if(smo*2 >= sm)break;
    }
    cnt2 = abs(cnt2 - (n-cnt2));

    if(cnt2 < cnt)swap(out2,out);

//    cout << ans << '\n';
    return out;
}
