#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> A)
{
    long long N=A.size(),s=0;
    vector<pair<int,int>> T;
    for(int i=0;i<N;i++)
    {
        T.push_back({i,A[i]});
        s+=A[i];
    }

    do
    {
        long long curr=0;
        for(int i=0;i<N;i++)
        {
            curr+=T[i].second;
            if(curr>=s/2)
            {
                if((N%2==0&&i==N/2)||(N%2==1&&(i==N/2||i==N/2+1)))
                {
                    for(int i=0;i<N;i++)A[i]=T[i].first;
                    return A;
                }
                break;
            }
        }
    }while(next_permutation(T.begin(),T.end()));

    return {};
}
