#include "partition.h"
//#include "grader.cpp"

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

auto val(vector<int> a) {
    int n = a.size();

    ll S = accumulate(a.begin(), a.end(), 0ll);

    ll cur = 0;

    for(int i = 0; i < n; i++) {
        cur += a[i];

        if(cur >= (S + 1) / 2) {
            break;
        }
    }

    return 2 * cur - S;
}

vector<int> solve(vector<int> a) {
    int n = a.size();

    vector<int> p(n);

    iota(p.begin(), p.end(), 0);

    ll my = 1e18;

    vector<int> ans;

    do {
        vector<int> b(n);
        for(int i = 0; i < n; i++) b[i] = a[p[i]];
        ll cur = val(b);
        if(cur < my) {
            ans = p;
            my = cur;
        }
    } while(next_permutation(p.begin(), p.end()));

//    cout << val(ans) << nl;

    return ans;
}

/**

1
5
1 2 4 8 16

1
5
524288 4 524288 1 1048576

**/
