#include "partition.h"
#pragma GCC optmize("Ofast", "unroll-loops")
#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
    {
        long long totalSum = accumulate(A.begin(), A.end(), 0);
        vector<int> v{};
        for(int i = 0; i < n; i++)
        {
            v.emplace_back(i);
        }
        vector<int> best_p(n, 0);
        long long best_dif = 2e9;
        do
        {
            long long sA = 0, sB = 0;
            for(int i = 0; i < n; i++)
            {
                if(sA * 2 >= totalSum)
                {
                    sB += A[v[i]];
                }
                else
                {
                    sA += A[v[i]];
                }
            }
            if(best_dif > abs(sB - sA))
            {
                for(int i = 0; i < n; i++)
                {
                    best_p[i] = v[i];
                }
                best_dif = abs(sB - sA);
            }
        } while(next_permutation(v.begin(), v.end()));
        return best_p;
    }
}
