#include "partition.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long

vector<int> tr;
vector<signed> res;

std::vector<signed> solve(std::vector<signed> A) {
    int n = A.size();
    int k = n/2;
    int idx = 0;
    ll s = 0; ll s2 = 0; tr.resize(n); res.resize(n);
    for (int i=0; i<n; i++) tr[i] = i; 
    vector<stack<int>> rt(30); int nn = 0;
    for (int i=0; i<n; i++){
        rt[__builtin_ctz(A[i])].push(i);
    }
    for (int i=0; i<30; i++){
        while (rt[i].size()){
            int s = rt[i].top(); rt[i].pop();
            tr[nn++] = s;
        }
    }
    for (int i=k; i<n; i++) s2+=A[tr[i]];
    for (int i=0; i<n; i++) s +=A[tr[i]];
     int nx = 0; 
    int f = 0;
    while (1){
        if (2*(s2 - A[tr[n-1-idx]]) < s){
            for (int i=0; i<idx; i++) res[nx++] = i;
            for (int i=k; i<n-idx; i++) res[nx++] = i;
            for (int i=idx; i<k; i++) res[nx++] = i;
            for (int i=n-idx; i<n; i++) res[nx++] = i;
            break;
        }
        if (idx >= k + (n%2)) {f=1; break;}
        s2 += A[tr[idx]] - A[tr[n-1-idx]]; idx++;
    }
    if ((n%2) && f){
        for (int i=0; i<n; i++) res[i] = i;
    }
    for (int i=0; i<n; i++) res[i] = tr[res[i]];
    return res;
}
