#include "partition.h"
#include <vector>
#include <utility>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
#include<random>
#include<unordered_map>
using namespace std;
using ll = long long;
#define V vector
#define VI V<int>
#define rep(i,a,b,step) for(int i=int(a);i<=int(b);i+=int(step))
#define repl(i,a,b,step) for(int i=int(a);i>=int(b);i-=int(step))
#define ff first
#define ss second
#define pq priority_queue
const int N = 26;
unordered_map<int, int>id;
std::vector<int> solve(std::vector<int> a) {
    if (id.empty())rep(i, 0, N - 1, 1)id[1 << i] = i;
    unordered_map<int, vector<int>>mp;
    int n = a.size(), l = 0, r = 0, mn = n, pt = n - 1, x = 0;
    ll sum = 0;
    VI ans(n), p(n);
    V<bool>used(n);
    rep(i, 0, n - 1, 1)sum += a[i], mp[id[a[i]]].push_back(i);
    for (auto& i : mp)for (auto& j : i.ss)
        p[l++] = j;
    l = 0;
    V<ll>pref(n);
    pref[0] = a[p[0]];
    rep(i, 1, n - 1, 1)pref[i] = pref[i - 1] + a[p[i]];
    repl(i, n - 1, 0, 1) {
        while (pt > i and 2 * (pref[pt - 1] - pref[i] + a[p[i]]) >= sum)pt--;
        if (2 * (pref[pt] - pref[i] + a[p[i]]) >= sum and abs(n - 2 * (pt - i + 1)) < mn) {
            mn = abs(n - 2 * (pt - i + 1));
            l = i;
            r = pt;
        }
    }
    rep(i, 0, r - l, 1)ans[i] = p[l + i], used[l + i] = 1;
    rep(i, r - l + 1, n - 1, 1) {
        while (x < n and used[x])x++;
        used[x] = 1;
        ans[i] = x;
    }
    return ans;
}