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

using ll = long long;
const int K = 16;
const int D = 1 << K;
const int N = 2e6;
int b[N], c[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 mx = std::max_element(a.begin(), a.end()) - a.begin();
    int* perm = perm1;
    int* nperm = perm2;
    std::iota(perm, perm + n, 0);
    std::swap(perm[mx], perm[n - 1]);
    if (n < 100) {
        std::sort(perm, perm + n - 1, [&](int x, int y) {
            return a[x] > a[y];
        });
    } else {
        std::copy(a.begin(), a.end(), b);
        b[mx] = 0;
        while (*std::max_element(b, b + n) > 0) {
            for (int i = 0; i < n; ++i) {
                c[i] = b[i] >> K;
                b[i] -= c[i] << K;
            }
            std::fill(cnt, cnt + D, 0);
            for (int i = 0; i < n - 1; ++i) ++cnt[b[perm[i]]];
            std::partial_sum(cnt, cnt + D, cnt);
            for (int i = n - 2; i >= 0; --i) {
                nperm[--cnt[b[perm[i]]]] = perm[i];
            }
            std::copy(c, c + n, b);
            std::swap(perm, nperm);
        }
        std::reverse(perm, perm + n - 1);
    }
    int L, R;
    {
        R = 0;
        ll s = 0;
        while (R < n - 1 && s + a[perm[n - 1 - R - 1]] <= (S - 1) / 2) {
            s += a[perm[n - 1 - R++ - 1]];
        }
    }
    {
        ll s = 0;
        L = 0;
        while (L < n - 1 && s < (S + 1) / 2 - a[mx]) s += a[perm[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;
            for (int i = 1; i <= cnt; ++i) s += a[perm[n - 1 - i]];
            for (int j = 0; j < n - 1; ++j) {
                int i = perm[j];
                if (ptr > 0 && s - a[perm[n - 1 - ptr]] + a[i] <= (S - 1) / 2) {
                    s = s - a[perm[n - 1 - ptr]] + a[i];
                    --ptr;
                    used[i] = true;
                }
            }
            for (int i = 1; i <= ptr; ++i) used[perm[n - 1 - i]] = true;
            std::vector<int> ret;
            ret.reserve(n);
            for (int i = 0; i < n; ++i) {
                if (used[i]) ret.push_back(i);
            }
            ret.push_back(mx);
            for (int i = 0; i < n; ++i) {
                if (i == mx) continue;
                if (!used[i]) ret.push_back(i);
            }
            return ret;
        }
    }
}