#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <assert.h>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'

using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#include "partition.h"

vector<pair<int,int>> a;
vector<pair<int,int>> ans;
long long ansc=1e18;
bool used[50];
long long s=0;
void rec(int i, int br, long long sum) {
    if(i==a.size()) {
        if(sum<s/2+s%2) return;
        long long c = br-(a.size()-br); c=abs(c);
        vector<int> test;
        for(int i = 0; i < a.size(); i++) {
            if(used[i]) test.push_back(a[i].first);
        }
        long long tests=0;
        for(int i = 0; i < test.size(); i++) {
            tests+=test[i];
            if(tests>=s/2+s%2 && i!=test.size()-1) return;
        }
        if(c<ansc) {
            //cout << "FOUND " << c << " " << br << endl << endl;

            ansc = c;
            ans.clear();
            for(int i = 0; i < a.size(); i++) {
                if(used[i]) ans.push_back(a[i]);
            }
            for(int i = 0; i < a.size(); i++) {
                if(!used[i]) ans.push_back(a[i]);
            }
            //for(auto x : ans) cout << x.first << " ";
            //cout << endl;
        }
        return;
    }
    used[i]=1;
    rec(i+1, br+1, sum+a[i].first);
    used[i]=0;
    rec(i+1, br, sum);
}
vector<int> solve(vector<int> A) {
    ans.clear();
    ansc=1e18;
    a.clear();
    s=0;
    for(int i = 0; i < A.size(); i++) {a.push_back({A[i], i}); s+=A[i];}
    sort(a.begin(), a.end());
    rec(0, 0, 0);
    //cout << ansc << endl;

    vector<int> ret;
    for(auto x : ans) ret.push_back(x.second);
    return ret;
}
/*
1
11
0 1 1 2 4 8 16 16 32 128 128
0 1 2 3 9 10 4 5 6 7 8
s/2=168

1
10
0 1 1 2 4 8 16 16 32 128
0 1 2 3 9 4 5 6 7 8

1
6
1 2 2 4 2048 2048
0 3 4 1 2 5
=> 1 4 2048 2 2 2048

1
5
1 2 2 4 2048
0 1 4 2 3







11
1
1
2
1 2
3
1 2 3
4
1 2 3 4
5
1 2 3 4 5
6
1 2 3 4 5 6
7
1 2 3 4 5 6 7
8
1 2 3 4 5 6 7 8
9
1 2 3 4 5 6 7 8 9
10
1 2 3 4 5 6 7 8 9 10
11
1 2 3 4 5 6 7 8 9 10 11




0
0 1 2
0 1 4 2 3
0 1 3 6 2 4 5
0 1 2 7 8 3 4 5 6
0 1 2 5 9 10 3 4 6 7 8
-----
0
0 1
0 1 4
0 1 3 6
0 1 2 7 8
0 1 2 5 9 10
-----

1 0
0 3 1 2
0 3 5 1 2 4
0 1 6 7 2 3 4 5
0 1 5 8 9 2 3 4 6 7




*/

