#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;
    vector<int> ans;
    for(int i=0;i<N;i++)
    {
        T.push_back({A[i],i});
        s+=A[i];
    }
    s++;
    s/=2;

    sort(T.begin(),T.end());

    for(int i=0;i<N;i++)
    {
        long long curr=0;
        for(int j=i;j<N;j++)
        {
            curr+=T[j].first;
            if(curr>=s)
            {
                int h=j-i+1;

                if((N%2==0&&h==N/2)||(N%2==1&&(h==N/2||h==N/2+1)))
                {
                    for(int t=i;t<=j;t++)ans.push_back(T[t].second);
                    for(int t=0;t<i;t++)ans.push_back(T[t].second);
                    for(int t=j+1;t<N;t++)ans.push_back(T[t].second);
                    return ans;
                }
                break;
            }
        }
    }

    return {};
}
