#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];
    vector<int>v;
    for(int i=0; i<(n+1)/2; i++) v.push_back(i+1);
    for(int i=0; i<n-(n+1)/2; i++) v.push_back(0);
    do {
        //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]) left.push_back(i);
            else right.push_back(i);
        }
        int flag=1;
        long long sum=0;
        for(int i=0; i<left.size()-1; i++) {
            sum += A[left[i]];
        }
        if(sum >= (S+1)/2) continue;
        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);
            //for(int x : ans) cout << x << " ";
            //cout << endl;
            return ans;
        }
    } while(next_permutation(v.begin(), v.end()));
}
