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

int n, total, best;

struct elem{
    int x, id;
    bool operator< (const elem& other) const{
        return x < other.x;
    }
}a[30];

vector<int> ales;
vector<int> ans;

bool viz[30];

void bkt(int i, ll sum){
    if(sum * 2 >= total){
        if(abs((int) ales.size() - (n - (int) ales.size())) < best){
            ans = ales;
            best = abs((int) ales.size() - (n - (int) ales.size()));
        }
        return;
    }
    if(i == n) return;
    //aleg i
    ales.push_back(a[i].id);
    bkt(i + 1, sum + a[i].x);
    ales.pop_back();
    bkt(i + 1, sum);
}

vector<int> solve(vector<int> v){
    n = v.size();
    for(int i = 0; i <= n; i++) viz[i] = 0;
    total = 0;
    best = n + 1;
    for(int i = 0; i < n; i++){
        a[i] = {v[i], i};
        total += v[i];
    }
    sort(a, a + n);
    ales.clear();
    bkt(0, 0);
    for(int i : ans){
        viz[i] = 1;
    }
    for(int i = 0; i < n; i++){
        if(!viz[i])
            ans.push_back(i);
    }
    return ans;
}
