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

constexpr int N = 33554432;
int val[N + 5];
bool did;

std::vector<int> solve(std::vector<int> a) {
    if (!did) {
        did = true;
        int vl = 1;
        for (int i = 0; i < 26; ++i) val[vl] = i, vl += vl;
    }
    int n = a.size();
    if (n == 1) return {0};
    std::vector<int> idx(n);
    std::vector<std::vector<int>> cnt(26);
    for (int i = 0; i < n; ++i) cnt[val[a[i]]].emplace_back(i);
    for (int i = 0, j = 0, vl = 1; i < 26; ++i) {
        for (auto u: cnt[i]) a[j] = vl, idx[j++] = u;
        vl += vl;
    }
    if (n == 2) return {1, 0};
    int64_t sum = 0;
    for (int i = 0; i < n; ++i) sum += a[i];
    int64_t sm = 0, nd = (sum + 1) / 2;
    int optl = 0, optr = (n + 1) / 2 - 2;
    for (int i = optl; i <= optr; ++i) sm += a[i];
    while (sm < nd - a.back()) {
        sm -= a[optl++];
        sm += a[++optr];
    }
    std::vector<int> res2;
    for (int i = optl; i <= optr; ++i) res2.emplace_back(idx[i]);
    res2.emplace_back(idx[n - 1]);
    for (int i = 0; i < optl; ++i) res2.emplace_back(idx[i]);
    for (int i = optr + 1; i + 1 < n; ++i) res2.emplace_back(idx[i]);
    return res2;
}
