#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 = 10;
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] = 31 - __builtin_clz(a[i]);
        // }
        std::copy(a.begin(), a.end(), b);
        for (int it = 0; it < 3; ++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];
    ++perm;
    for (int i = 0; i < n - 1; ++i) b[i] = a[perm[i]];
    int cnt = 0;
    ll s = 0;
    while (cnt < (n - 1) / 2 && s + b[n - 1 - cnt - 1] <= (S - 1) / 2) s += b[n - 1 - cnt++ - 1];
    int ptr = cnt;
    while (ptr > 0) {
        ll ns = s + b[cnt - ptr] - b[n - 1 - ptr];
        if (ns <= (S + 1) / 2) {
            s = ns;
            --ptr;
        } else {
            break;
        }
    }
    assert(s >= (S + 1) / 2 - a[mx]);
    std::vector<int> ret(n);
    int c = 0;
    for (int i = 0; i < cnt - ptr; ++i) ret[c++] = perm[i];
    for (int i = 1; i <= ptr; ++i) ret[c++] = perm[n - 1 - i];
    ret[c++] = mx;
    for (int i = cnt - ptr; i < n - 1 - ptr; ++i) ret[c++] = perm[i];
    return ret;
}