#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
const int MAXN=1e7;
int a[MAXN+1];

int nr;

int optmask=0,ans=INT_MAX;
long long S=0;

void bkt(int idx,int mask,int maxpath,long long sum,int bits) {
    if(idx==nr) {
        if(2*sum>S&&2*(sum-maxpath)<S) {
            if(abs(nr-2*bits)<ans) {
                ans=abs(nr-2*bits);
                optmask=mask;
            }
        }
        return;

    }
    bkt(idx+1,mask|(1<<idx),max(maxpath,a[idx]),sum+a[idx],bits+1);
    bkt(idx+1,mask,maxpath,sum,bits);
}

vector<int> solve(vector<int> A) {
    int n=A.size();
    for(int i=0; i<n; i++) {
        a[i]=A[i];
        S+=a[i];
    }
    nr=n;
    bkt(0,0,0,0,0);
    vector<int>res;
    int mx=0;
    for(int i=0; i<n; i++) {
        if(optmask&(1<<i)) {
            res.push_back(i);
            mx=max(mx,a[i]);
        }
    }
    int cnt=0,pos;
    for(int i=0; i<n; i++) {
        if((optmask&(1<<i))&&a[i]==mx) {
            pos=cnt;
            break;
            cnt++;
        }
    }
    swap(res[res.size()-1],res[pos]);
    for(int i=0; i<n; i++) {
        if(!(optmask&(1<<i))) {
            res.push_back(i);
        }
    }
    return res;
}
/*
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t ;
    for (int test=1; test<=t; test++) {
        int n;
        cin >> n ;
        vector <int> a(n);
        for (int i=0; i<n; i++) {
            cin >> a[i] ;
        }

        for (auto ind : solve(a)) {
            cout << ind << " ";
        }
        cout << endl ;
    }
    cout << endl ;
    return 0;
}

*/
