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

const int MAXN = 1e7 + 5;
// maxsum

std::vector<int> solve(std::vector<int> A)
{
    vector <int> ans;
    vector <int> can(MAXN);
    vector <int> br(MAXN);
    vector <bool> used(MAXN);
    //sort(A.rbegin(), A.rend());
    int Rsum = 0, n = A.size(), sum = 0;
    can[0] = true;
    for (int i = 0; i < n; i++)
    {
        for (int j = Rsum; j >= 0; j--)
        {
            if (can[j] != 0 && can[j + A[i]] == 0)
            {
                can[j + A[i]] = i;
            }
        }
        Rsum += A[i];
        sum += A[i];
    }
    int ind = ceil(sum / 2.0);
    while (ind < sum)
    {
        if (can[ind] != 0)
        {
            break;
        }
        ind++;
    }
    //cout << "1: " << ind << endl;
    //cout << "2: " << sum - ind << endl;
    int sum1 = 0;
    while (ind >= 0)
    {
        if (can[ind] != 0)
        {
            break;
        }
        ind--;
    }
    for (int j = ind; j > 0; )
    {
        if (can[j] != 0)
        {
            used[can[j]] = true;
            ans.push_back(can[j]);
            //ans.push_back(A[can[j]]);
            j -= A[can[j]];
        }
        else
        {
            j--;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (!used[i])
        {
            ans.push_back(i);
            //ans.push_back(A[i]);
        }
    }
    return ans;
}
