#include <bits/stdc++.h>
#pragma GCC optimize( "unroll-loops,Ofast,fast-math" )
#pragma target( "avx2" )
#include "partition.h"
using namespace std;

const int MAXN = 2e6;
const int MSK = ( 1 << 20 ) + 1;

int n;
long long sum[MSK + 1];
int maxi[MSK + 1] , bits[MSK + 1];
bool dp[MSK + 1];
void init() {
    int i;
    if( bits[1] == 1 )
        return;
    bits[0] = 0;
    for( i = 1 ; i <= MSK ; i++ )
        bits[i] = bits[i & ( i - 1 )] + 1;
}
vector< int >solve( vector< int >a ) {
    int i , mskans , msk , j , cop , ok , nrmin;
    long long s;
    vector< int >ans;
    n = a.size();
    init();
    //cout << bits[15] << "PULA\n";
    if( n == 1 ) {
        ans.push_back( 0 );
        return ans;
    }
    a.push_back( 0 );
    s = 0;
    nrmin = n + 1;
    for( i = 0 ; i < n ; i++ )
        s += a[i];
    s = ( s + 1 ) / 2;
    int allmsk = ( 1 << n ) - 1;
    for( msk = 0 ; msk < ( 1 << n ) ; msk++ ) {
        maxi[msk] = n;
        sum[msk] = 0;
        for( j = 0 ; ( 1 << j ) <= msk ; j++ )
            if( msk & ( 1 << j ) ) {
                sum[msk] += a[j];
                //cout << msk << ' ' << j << ' ' << a[j] << '\n';
                if( a[j] > a[maxi[msk]] )
                    maxi[msk] = j;
            }
        //cout << msk << ' ' << sum[msk] << ' ' << maxi[msk] << '\n';
    }
    // imi tin sume pe submasti si caut cea mai buna submasca la care daca ii mai adaug un element sa aibe suma mai mare ca i
    for( msk = 0 ; msk < ( 1 << n ) ; msk++ ) {
        int nr = a[maxi[allmsk ^ msk]];
        if( sum[msk] < s && sum[msk] + nr >= s ) {
            int cnt = bits[msk];
            cnt++;
            if( abs( cnt - ( n - cnt ) ) < nrmin ) {
                nrmin = abs( cnt - ( n - cnt ) );
                mskans = msk;
            }
        }
        if( nrmin == n % 2 )
            break;
    }
    for( j = 0 ; ( 1 << j ) <= mskans ; j++ )
        if( ( 1 << j ) & mskans )
            ans.push_back( j );
    //cout << mskans << ' ' << ( mskans ^ allmsk ) << ' ' << maxi[mskans ^ allmsk] << '\n';
    ans.push_back( maxi[mskans ^ allmsk] );
    mskans ^= ( 1 << maxi[mskans ^ allmsk] );
    //cout << mskans << '\n';
    for( i = 0 ; i < n ; i++ )
        if( !( ( 1 << i ) & mskans ) )
            ans.push_back( i );
    //cout << nrmin << '\n';
    return ans;
}
