#include "partition.h"

#define ll long long

#include <bits/stdc++.h>

using namespace std;

ll n, v[2000005] = { 0 };
ll sum = 0, sum_total = 0, nr = 0, best, pos_mx = 0;
ll crt[2000005] = { 0 };
vector<int> ans;

void bkt(int pos) {
    if(best <= 1 || sum - v[pos_mx] >= (sum_total + 1) / 2) {
        return;
    }
    if(pos == n + 1) {
        if(sum >= (sum_total + 1) / 2 && abs(n - nr - nr) < best) {
            best = abs(n - nr - nr);
            ans.clear();
            for(int i = 1; i <= n; i++) {
                if(crt[i] == 1 && i != pos_mx) {
                    ans.push_back(i - 1);
                }
            }
            ans.push_back(pos_mx - 1);
            for(int i = 1; i <= n; i++) {
                if(crt[i] == 0) {
                    ans.push_back(i - 1);
                }
            }
        }

        // cout << abs(n - nr - nr) << '\n';
        // for(int i = 1; i <= n; i++) {
        //         if(crt[i] == 1 && i != pos_mx) {
        //             cout << i - 1 << ' ';
        //         }
        //     }
        //     cout << pos_mx - 1 << ' ';
        //     cout << "aici ";
        //     for(int i = 1; i <= n; i++) {
        //         if(crt[i] == 0) {
        //             cout << i - 1 << ' ';
        //         }
        //     }
        // cout << '\n';

        return;
    }
    for(int bit = 1; bit >= 0; bit--) {
        crt[pos] = bit;
        int prev = pos_mx;
        if(bit == 1) {
            crt[pos] = 1;
            sum += v[pos];
            nr++;
            if(v[pos] > v[pos_mx]) {
                pos_mx = pos;
            }
        }
        bkt(pos + 1);
        if(bit == 1) {
            crt[pos] = 0;
            sum -= v[pos];
            nr--;
            pos_mx = prev;
        }
    }
}

std::vector<int> solve(std::vector<int> A) {

    sum = sum_total = nr = pos_mx = 0;

    n = A.size();
    for(int i = 1; i <= n; i++) {
        v[i] = A[i - 1];
        sum_total += v[i];
    }
    best = n;

    ans.push_back(0);
    bkt(1);
    // cout << best << '\n';

    for(int i = 1; i <= n; i++) {
        v[i] = crt[i] = 0;
    }

    return ans;

}