#include "partition.h"
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>
using namespace std;

int _n, sum, res;
// vector<pair<int, int>> V;
vector<int> ans, A;
// set<int> st;

int calc(vector<int> ind) {
    int S = 0, T = (sum + 1) / 2;
    int i;
    for (i = 0; i < _n; i++) {
        S += A[ind[i]];
        if (S >= T)
            break;
    }
    int j = _n - i - 1;
    // cerr << i + 1 << '|' << j << endl;
    return abs((i + 1) - j);
}

void systemd() {
    res = _n + 1;
    sum = 0;
    // V.resize(_n);
    // mp.clear();
}

void solve2() {
    for (int bit = 0; bit < (1 << _n); bit++) {
        vector<int> cur;
        for (int i = 0; i < _n; i++) {
            if ((1 << i) & bit) {
                cur.push_back(i);
            }
        }
        sort(cur.begin(), cur.end(), [&](int l, int r) {
            return A[l] < A[r];
        });
        for (int i = 0; i < _n; i++) {
            if (!((1 << i) & bit)) {
                cur.push_back(i);
            }
        }
        // cerr << res << ' ' << calc(cur) << endl;
        if (calc(cur) <= res) {
            res = calc(cur), ans = cur;
        }
    }
}

std::vector<int> solve(std::vector<int> A_) {
    _n = A_.size();
    systemd();
    A = A_;
    for (int &a : A)
        sum += a;
    solve2();
    return ans;
}

/*
1
4
2 6 4 4
 */
