#include "partition.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long llong;

const int MAXN = 2e6 + 10;

int n;

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

    llong sum = 0;

    vector < int > p(n);

    for(int i = 0; i < n; i++)
    {
        p[i] = i;
        sum += A[i];
    }

    int mindiff = n;
    vector < int > ans(n);

    do
    {
        llong cur = 0;

        int diff = 0;

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

            if(2LL * cur >= sum)
            {
                diff = abs((i + 1) - (n - i - 1));
                break;
            }
        }

        if(mindiff > diff)
        {
            mindiff = diff;
            ans = p;
        }

    }while(next_permutation(p.begin(), p.end()));

    return ans;
}
