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

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

int n;
bool viz[MSK + 1];
map< int , int >f;
map< int , int >f2;
vector< int >pos1 , pos2;
vector< int >solve( vector< int >a ) {
    int i , mskans , msk , j , cop , ok;
    long long s , sum;
    vector< int >ans;
    n = a.size();
    sum = 0;
    for( i = 0 ; i < n ; i++ )
        sum += a[i];
    int nrmin = n;
    //cout << sum << '\n';
    msk = 15;
    for( msk = 0 ; msk < ( 1 << n ) ; msk++ ) {
        s = 0;
        ok = 1;
        for( cop = msk ; cop ; cop = ( cop - 1 ) & msk )
            if( viz[cop] == 1 )
                ok = 0;
        if( ok == 0 )
            continue;
        for( j = 0 ; ( 1 << j ) <= msk ; j++ )
            if( ( 1 << j ) & msk )
                s += a[j];
        int cnt = __builtin_popcount( msk );
        if( s >= ( sum + 1 ) / 2 && abs( cnt - ( n - cnt ) ) < nrmin ) {
            nrmin = abs( cnt - ( n - cnt ) );
            mskans = msk;
        }
        if( s >= sum / 2 / 2 )
            viz[msk] = 1;
    }
    //cout << mskans << '\n';
    for( i = 0 ; i < n ; i++ )
        if( ( 1 << i ) & mskans )
            ans.push_back( i );
    for( i = 0 ; i < n ; i++ )
        if( !( ( 1 << i ) & mskans ) )
            ans.push_back( i );
    return ans;
}
