#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second

const int mxN = 2e6 + 5;
int n;
vector<int> cnt[30];
pair<int, int> a[mxN];

std::vector<int> solve(std::vector<int> A) {
    n = A.size();
    int sz = (n + 1) / 2,idx = 0;
	ll sum = 0,curr = 0;
	for(int i = 0; i < 26; i++) cnt[i].clear();
    for(int i = 0; i < n; i++){
    	cnt[int(log2(A[i]))].pb(i);
		a[i].ff = A[i];
    	a[i].sd = i;
    	sum += a[i].ff;
	}
//    if(n <= 100000) sort(a, a + n);
    for(int i = 0; i < 26; i++){
    	int val = (1 << i);
    	for(auto it : cnt[i]) a[idx++] = {val, it};
	}
//	for(int i = 0; i < n; i++) cout << a[i].ff << ' ';
//	cout << '\n';
    for(int i = 0; i < sz; i++) curr += a[i].ff;
    vector<int> ans;
    if(2 * curr >= sum){
    	for(int i = 0; i < n; i++) ans.pb(a[i].sd);
    	return ans;
	}
	for(int i = 0; i < sz; i++){
		curr -= a[sz - i - 1].ff - a[n - i - 1].ff;
		if(curr * 2 >= sum){
			for(int j = 0; j < sz - i - 1; j++) ans.pb(a[j].sd);
			for(int j = n - i - 1; j < n; j++) ans.pb(a[j].sd);
			for(int j = sz - i - 1; j < n - i - 1; j++) ans.pb(a[j].sd);
			return ans;
		}
	}
}
