#include "partition.h"
// peta podzadacha?
#include<algorithm>
using namespace std;
std::vector<int> solve(std::vector<int> A) {
    vector<int> ans;
    int n = A.size(), sum = 0;
    for(int a : A) sum += a;
    if(sum % 2 == 1) sum = (sum + 1) / 2;
    vector<pair<int, int>> B, ANS;
    for(int i = 0; i < n; ++i){
        B.push_back({A[i], i});
    }
    int best_diff = n + 2;
    while(next_permutation(B.begin(), B.end())){
        int s = 0;
        for(int i = 0; i < n; ++i){
            s += B[i].first;
            if(s >= sum){
                int zhena1 = i + 1;
                int zhena2 = n - zhena1;
                int diff = abs(zhena1 - zhena2);
                if(diff < best_diff){
                    best_diff = diff;
                    ANS = B;
                }
            }
        }
    }
    for(int i = 0; i < n; ++i){
        ans.push_back(ANS[i].second);
    }
    return ans; // brat tova trqbwa da bachka za tozi tup sluchi, wtf
}
