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

// maxsum

std::vector<int> solve(std::vector<int> A)
{
    const int maxN = 1e5 + 5;
    vector <int> ans;
    vector <int> can(maxN);
    vector <int> br(maxN);
    vector <bool> used(maxN);
    sort(A.begin(), A.end());
    int n = A.size();
    int sumAll = 0;
    for (int i = 0; i < n; i++)
    {
        sumAll += A[i];
    }
    int ind = 0, sum = 0, mid = ceil(sumAll / 2.0);
    while (true)
    {
        sum += A[n - ind - 1];
        //cout << sum << endl;
        ans.push_back(n - ind - 1);
        used[n - ind - 1] = true;
        if (sum >= mid)
        {
            break;
        }
        sum += A[ind];
        ans.push_back(ind);
        used[ind] = true;
        if (sum >= mid)
        {
            break;
        }
        ind++;
    }
    for (int i = 0; i < n; i++)
    {
        if (!used[i]) ans.push_back(i);
    }
    return ans;
}
