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

#define ll long long

ll INF = 1e17;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    vector<int> bestA;
    ll currAns = INF;
    ll s = 0;
    for (auto x: A) s += x;
    for (int i = 0; i < (1 << n); i++) {
        vector<int> uses;
        ll tot = 0;
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                uses.push_back(j);
                tot += A[j];
            }
        }
        if (tot < currAns && tot >= (s + 1) / 2) {
            currAns = tot;
            bestA = uses;
        }
    }
    vector<bool> inA(n, false);
    for (auto x: bestA) inA[x] = true;
    vector<pair<int, int>> ff, ss;
    for (int i = 0; i < n; i++) {
        if (inA[i]) ff.push_back({A[i], i});
        else ss.push_back({A[i], i});
    }
    sort(ff.rbegin(), ff.rend());
    vector<int> fin;
    for (auto [vv, id]: ff) fin.push_back(id);
    for (auto [vv, id]: ss) fin.push_back(id);
    return fin;
}
