#include "partition.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <deque>
#include <math.h>
#include <array>
#include <set>
#include <string>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = int;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

const ll INF = 1e18;

inline ll get_log(ll a) {
    ll num = 0;
    while (a > 0) {
        a >>= (ll)1;
        num++;
    }
    return num - 1;
}

vector<int> solve(vector<int> A) {
    ll n = A.size();
    vpll arr;
    double sum = 0;
    vvll bucket(26);
    rep(i, 0, n) {
        sum += (double)A[i];
        A[i] = log2(A[i]);
        bucket[A[i]].push_back(i);
        //arr[i] = { A[i], i };
    }
    rep(i, 0, bucket.size()) {
        rep(j, 0, bucket[i].size()) {
            arr.push_back({ ((ll)1 << i), bucket[i][j]});
        }
    }
    //sort(arr.begin(), arr.end());
    sum /= 2;
    //bucket_sort(arr);
    ll left = 0, right = -1;
    long long cur_sum = 0;
    ll best_dif = 0;
    if (n % 2 == 1) best_dif = 1;
    while (right < n - 1) {
        if (cur_sum >= sum) {
            break;
        }
        right++;
        ll val = arr[right].first;
        ll idx = arr[right].second;
        cur_sum += val;
        if (right - left + 1 - (n - (right - left + 1)) == best_dif) {
            if (cur_sum >= sum) break;
            cur_sum -= arr[left].first;
            left++;
        }
    }
    vector<int> ans(n);
    ll pos = 0;
    rep(i, left, right + 1) {
        ans[pos] = arr[i].second;
        pos++;
    }
    rep(i, 0, left) {
        ans[pos] = arr[i].second;
        pos++;
    }
    rep(i, right + 1, n) {
        ans[pos] = arr[i].second;
        pos++;
    }
    return ans;
}
