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

const int N=2e6+5;
int n;
ll all=0;
vector<pair<int, int>> v;
vector<int> ans;

void add(int l, int r, vector<pair<int, int>> &a) {
    for(int i=l; i<=r; i++)
        ans.push_back(a[i].second);
}
void clr() {
    ans.clear();
    v.clear();
    all=0;
}

std::vector<int> solve(std::vector<int> A) {
    clr();
    n=A.size();
    for(int i=0; i<n; i++)
        v.push_back({A[i], i});
    for(int i=0; i<n; i++)
        all+=A[i];
    int mn=2*n;
    for(int msk=0; msk<(1<<n); msk++) {
        ll curr=0;
        int cnt=0, mx=0, id=0;
        vector<int> c;
        for(int b=0; b<n; b++) {
            if(msk&(1<<b)) {
                curr+=v[b].first;
                cnt++;
                if(mx<v[b].first) {
                    mx=v[b].first;
                    id=b;
                }
            }
        }
        if(curr>=(all+1)/2&&curr-mx<(all+1)/2) {
            if(mn>abs(n-cnt-cnt)) {
                mn=abs(n-2*cnt);
                for(int b=0; b<n; b++) {
                    if(b==id)
                        continue;
                    if(msk&(1<<b)) {
                        c.push_back(v[b].second);
                    }
                }
                c.push_back(v[id].second);
                for(int b=0; b<n; b++) {
                    if((msk&(1<<b))==0)
                        c.push_back(v[b].second);
                }
                ans=c;
            }
        }
    }
    return ans;
}
