#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include "partition.h"
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define ll long long
using namespace std;

vector<int> solve(vector<int> a) {
    int n = a.size();
    if (n > 20) {
        cout << a[n+1];
    }
    double S = 0;
    for (int &i : a) S += i;
    S /= 2;
    int best = 0, k=0;
    for (int mask = 0; mask < (1 << n); mask++) {
        ll x=0, mx=0;
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                x += a[i];
                c++;
                mx = max(mx, 1LL * a[i]);
            }
        }
        if (1. * x >= S && 1. * x - mx < S) {
            if (abs(n - k * 2LL) > abs(n - c * 2LL)) {
                k = c;
                best = mask;
            }
        }
    }
    vector <pair<int, int>> l, r;
    for (int i = 0; i < n; i++) {
        if (best & (1 << i)) l.pb({a[i], i});
        else r.pb({a[i], i});
    }
    sort(all(l));
    sort(all(r));
    vector <int> ans;
    for (auto &i : l) ans.pb(i.ss);
    for (auto &i : r) ans.pb(i.ss);
    return ans;
}
