#include "partition.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 3e6 + 10;
//vector < pair < int, int > > g;
int n,  used[maxn];
vector < pair < int, int > > g;
int is[maxn];
int mindif;
long long total = 0;
vector < int >ans;
void check(int cnt0, int cnt1, long long sumis, long long sumisnt)
{
    cnt0 = (n - cnt1);
    int currdiff = abs(cnt0-cnt1);
    if(currdiff < mindif)
    {
        vector < int > curr;
        for (int i = 0; i < n; ++ i)
        {
            if(is[i] == 1)curr.pb(g[i].second);
           // curr.pb(g[i].first);
        }
        for (int i = 0; i < n; ++ i)
        {
            if(!is[i])curr.pb(g[i].second);
        }
        ans = curr;
        mindif = currdiff;
    }
}
void gen(int pos, int cnt0, int cnt1, long long sumis, long long sumisnt)
{
    if(sumisnt * 2 > total)return;
    if(sumis * 2 >= total)
    {

        check(cnt0, cnt1, sumis, sumisnt);
        return;
    }
    if(pos == n)return;

    is[pos] = 0;
    gen(pos+1,cnt0 +1, cnt1, sumis, sumisnt + g[pos].first );
    is[pos] = 1;
    gen(pos+1, cnt0, cnt1+1, sumis + g[pos].first, sumisnt);
    is[pos] = 0;
}
std::vector<int> solve(std::vector<int> A)
{

    n = A.size();
     total = 0;
     g.clear();
    for (int i = 0; i < n; ++ i)
    {
        total += A[i];
        g.pb(make_pair(A[i], i));
    }
    sort(g.begin(), g.end());
    for (int i = 0; i < n; ++ i)
        used[i] = 0;
    mindif = n;
    gen(0, 0, 0, 0, 0);
  //  cout << mindif << endl;
    return ans;
}
