#include "partition.h"
#include <bits/stdc++.h>
#define abs(x) ((x) < 0 ? -(x) : (x))
#define mkp make_pair
#define int long long

using namespace std;

int n, sum;
int v[2000005];
vector<signed> best;
int score;
mt19937 mt(67676767);
int smt[100];

void tryThis(int lft) {
    int s = 0;
    for(int i=0; i<n; ++i) {
        s += v[smt[lft + i]];
        if(s >= (sum + 1) / 2) {
            if(abs(i + 1 - (n - i - 1)) < score) {
                score = abs(i + 1 - (n - i - 1));
                best.resize(n);
                for(int i=0; i<n; ++i) {
                    best[i] = smt[lft + i];
                }
            }
            return;
        }
    }
}

vector<signed> solve(vector<signed> _v) {
    n = _v.size();
    if(n == 1) {
        return {0};
    }
    for(int i=0; i<n; ++i) {
        v[i] = _v[i];
    }
    score = n;
    sum = 0;
    for(int i=0; i<n; ++i) {
        sum += v[i];
    }
//    sort(perm.begin(), perm.end(), [](int a, int b){return v[a] < v[b];});
//    sort(v.begin(), v.end());
//        deque<int> vec;
    for(int m = 0; m < (1 << n); ++m) {
        int b = __builtin_popcount(m);
        if(abs(b - n / 2) > 3) {
            continue;
        }
        int lft = 50, rgt = 49;
        for(int i=0; i<n; ++i) {
            if(m & (1 << i)) {
                smt[--lft] = i;
            } else {
                smt[++rgt] = i;
            }
        }
        sort(smt + lft, smt + 50, [](int a, int b){return v[a] < v[b];});
        tryThis(lft);
    }
//    cout << score << endl;
    return best;
}
