#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
using namespace std;

const int nmax=2e6;

pii v[nmax+1];

bool taken[nmax+1],best_answer[nmax+1];
int n,best;
ll sum;

void bkt(int i,int n,ll cur_sum,int cnt){
    if(cur_sum>=sum/2 || i==n){
        if(i==n)
            return;
        int dif=abs(cnt-n);
        if(dif<best){
            best=dif;
            for(int i=0;i<n;i++)
                best_answer[i]=taken[i];///daca sunt in prima jumatate
        }
        return;
    }
    ///take
    taken[i]=1;
    bkt(i+1,n,cur_sum+v[i].first,cnt+1);
    ///not take
    taken[i]=0;
    bkt(i+1,n,cur_sum,cnt);

}

vector<int> solve(vector<int>A){
    sum=0;
    best=1e9;
    n=A.size();
    vector<int>answer;
    for(int i=0;i<n;i++){
        v[i].first=A[i];
        sum+=A[i];
        v[i].second=i;
    }
    bkt(0,n,0,0);
    for(int i=0;i<n;i++)
        if(best_answer[i])
            answer.pb(v[i].first);
    for(int i=0;i<n;i++)
        if(!best_answer[i])
            answer.pb(v[i].first);
    return answer;

}