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

bool cmp(pair<__int128_t, long long> x, pair<__int128_t, long long> y)
{
    return x.first > y.first;
}

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

    if(n > 25)
    {
        vector<pair<__int128_t, long long>> cA{};
        for(long long i = 0; i < n; i++)
        {
            cA.emplace_back(A[i], i);
        }
        
        sort(cA.begin(), cA.end(), cmp);
        
        __int128_t sD = 0, sM = 0;
        vector<long long> D{}, M{};
        for(long long i = 0; i < n; i++)
        {
            if(sD > sM)
            {
                sM += cA[i].first;
                M.emplace_back(cA[i].second);
            }
            else
            {
                sD += cA[i].first;
                D.emplace_back(cA[i].second);
            }
        }

        // cout << abs(sD - sM) << "\n";

        for(long long i = 0; i < D.size(); i++)
        {
            A[i] = D[i];
        }
        for(long long i = 0; i < M.size(); i++)
        {
            A[i + D.size()] = M[i];
        }

        return A;
    }
    else
    {
        __int128_t totalSum = 0;
        for(int i = 0; i < n; i++)
        {
            totalSum += A[i];
        }
        vector<int> v;
        for(int i = 0; i < n; i++)
        {
            v.emplace_back(i);
        }
        vector<int> best_p;
        int best_dif = 2e9;
        do
        {
            __int128 sA = 0, sB = 0;
            for(int i = 0; i < v.size(); i++)
            {
                if(sA * 2 < totalSum)
                {
                    sA += A[v[i]];
                }
                else
                {
                    break;
                }
            }
            sB = totalSum - sA;
            if(sA > sB)
            {
                __int128 tr = sB;
                sB = sA;
                sA = tr;
            }
            if(best_dif > sB - sA)
            {
                best_p = v;
                best_dif = sB - sA;
            }
        } while(next_permutation(v.begin(), v.end()));
        // cout << best_dif << "\n";
        return best_p;
    }
}
