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

// maxsum

std::vector<int> solve(std::vector<int> A)
{
    int n = A.size();
    int sumAll = 0;
    for (int i = 0; i < n; i++)
    {
        sumAll += A[i];
    }
    if (n == 1)
    {
        return {A[0]};
    }

    int bestDiff = 1e9;
    vector <int> bestAns;
    for (int mask = 0; mask <= (1 << n); mask++)
    {
        vector <int> part;
        int sumPart = 0;
        for (int i = 0; i < n; i++)
        {
            if (mask & (1 << i))
            {
                part.push_back(i);
                sumPart += A[i];
            }
        }
        if (sumPart >= ceil(sumAll / 2.0))
        {
            if (bestDiff > (abs ((n / 2) - (int)part.size())))
            {
                bestDiff = (abs ((n / 2) - (int)part.size()));
                bestAns = part;
            }
        }

    }
    vector <bool> used;
    used.resize(1e6);
    for (int i = 0; i < bestAns.size(); i++)
    {
        used[bestAns[i]] = true;
    }
    for (int i = 0; i < n; i++)
    {
        if (!used[i]) bestAns.push_back(i);
    }

    return bestAns;
}
