#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    long long S=0;
    for(int i=0; i<n; i++) S += A[i];

    for(int i=0; i<(1 << n); i++) {
        vector<int>v;
        for(int bit=0; bit<n; bit++) {
            if((1 << bit) & i) v.push_back(1);
            else v.push_back(0);
        }
        //for(int x : v) cout << x << " ";
        //cout << endl;
        vector<int>left;
        vector<int>right;
        for(int i=0; i<v.size(); i++) {
            if(v[i]>0) left.push_back(i);
            else right.push_back(i);
        }
        long long sum=0;
        if(left.size() >= 2) {
            for(int i=0; i<left.size()-1; i++) {
                sum += A[left[i]];
            }
        }
        if(sum >= (S+1)/2) continue;
        if(left.size()) sum += A[left[left.size()-1]];
        if(sum >= (S+1)/2) {
            vector<int>ans;
            for(int x : left) ans.push_back(x);
            for(int x : right) ans.push_back(x);
            return ans;
        }
    }
}
