#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();
    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;
}
