#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;
vector<int> v;
vector<signed> best;
int score;
mt19937 mt(67676767);

void tryThis(vector<int> vec) {
    int s = 0;
    for(int i=0; i<n; ++i) {
        s += v[vec[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] = vec[i];
                }
            }
            return;
        }
    }
}

vector<signed> solve(vector<signed> _v) {
    n = _v.size();
    if(n == 1) {
        return {0};
    }
    v.resize(n);
    for(int i=0; i<n; ++i) {
        v[i] = _v[i];
    }
    score = n;
    sum = accumulate(v.begin(), v.end(), 0);
    sort(v.begin(), v.end());
    for(int m = 0; m < (1 << n - 1); ++m) {
        vector<int> vec, v2;
        for(int i=0; i<n-1; ++i) {
            if(m & (1 << i)) {
                vec.push_back(i);
            } else {
                v2.push_back(i);
            }
        }
        vec.push_back(n-1);
        for(int i : v2) {
            vec.push_back(i);
        }
        tryThis(vec);
    }
    return best;
}
