#include<iostream>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
#include "partition.h"

using ll = long long;
const int K = 6;
const int D = 1 << K;
const int N = 2e6;
int b[N], perm1[N], perm2[N], cnt[D];
bool used[N];

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    if (n == 1) return {0};
    ll S = std::accumulate(a.begin(), a.end(), 0ll);
    int* perm = perm1;
    int* nperm = perm2;
    std::iota(perm, perm + n, 0);
    if (n < 0) {
        std::sort(perm, perm + n, [&](int x, int y) {
            return a[x] > a[y];
        });
    } else {
        for (int i = 0; i < n; ++i) {
            b[i] = 32 - __builtin_clz(a[i]);
        }
        // std::copy(a.begin(), a.end(), b);
        for (int it = 0; it < 1; ++it) {
            #pragma GCC ivdep
            for (int i = 0; i < D; ++i) cnt[i] = 0;
            #pragma GCC ivdep
            for (int i = 0; i < n; ++i) ++cnt[b[perm[i]] & (D - 1)];
            std::partial_sum(cnt, cnt + D, cnt);
            for (int i = n - 1; i >= 0; --i) {
                nperm[--cnt[b[perm[i]] & (D - 1)]] = perm[i];
                b[perm[i]] >>= K;
            }
            std::swap(perm, nperm);
        }
        std::reverse(perm, perm + n);
    }
    int mx = perm[0];
    std::rotate(perm, perm + 1, perm + n);
    for (int i = 0; i < n - 1; ++i) b[i] = a[perm[i]];
    int L, R;
    {
        R = 0;
        ll s = 0;
        while (R < n - 1 && s + b[n - 1 - R - 1] <= (S - 1) / 2) {
            s += b[n - 1 - R++ - 1];
        }
    }
    {
        ll s = 0;
        L = 0;
        while (L < n - 1 && s < (S + 1) / 2 - a[mx]) {
            s += b[L++];
        }
        L--;
    }
    for (int cnt = (n - 1) / 2; cnt >= 0; --cnt) {
        if (L <= cnt && cnt <= R) {
            std::fill(used, used + n, false);
            int ptr = cnt;
            ll s = 0;
            #pragma GCC ivdep
            for (int i = 1; i <= cnt; ++i) s += b[n - 1 - i];
            for (int i = 0; i < n - 1; ++i) {
                if (ptr > 0 && s - b[n - 1 - ptr] + b[i] <= (S - 1) / 2) {
                    s = s - b[n - 1 - ptr] + b[i];
                    --ptr;
                    used[perm[i]] = true;
                }
            }
            #pragma GCC ivdep
            for (int i = 1; i <= ptr; ++i) used[perm[n - 1 - i]] = true;
            std::vector<int> ret(n);
            ptr = 0;
            for (int i = 0; i < n; ++i) {
                if (used[i]) {
                    ret[ptr++] = i;
                }
            }
            ret[ptr++] = mx;
            for (int i = 0; i < n; ++i) {
                if (i == mx) continue;
                if (!used[i]) {
                    ret[ptr++] = i;
                }
            }
            return ret;
        }
    }
}