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

using namespace std;

#define for0(i, n) for (ll i = 0; i < n; i++)
#define for1(i, n) for (ll i = 1; i < n; i++)
#define rfor0(i, n) for (ll i = n - 1; i >= 0; i--)
#define be(x) x.begin()
#define en(x) x.end()
#define all(x) be(x), en(x)
#define sz(x) x.size()
#define pb push_back
#define con continue
#define ret return

typedef long long ll;
typedef vector<ll> vll;

const int N = 2e6 + 5, C = 10, M = 1 << C;

int a[N], c[N], p[N], _p[N];
int cnt[M + 1];

#pragma GCC optimize("O3")
#pragma GCC target("avx2,sse4")

std::vector<int> solve(std::vector<int> _a) {
    int n = sz(_a);
    for0(i, n) a[i] = _a[i];
    ll s = accumulate(a, a + n, 0ll);
    iota(p, p + n, 0);
    if (n <= 200) {
        sort(p, p + n, [&](int x, int y) { return a[x] < a[y]; });
    } else {
        for (int bt = 0; bt < 3; bt++) {
            for (int i = 0; i < M; i++) cnt[i] = 0;
            for (int i = 0; i < n; i++) {
                c[p[i]] = a[p[i]];
                c[p[i]] >>= (10 * bt);
                c[p[i]] &= (M - 1);
                cnt[c[p[i]]]++;
            }
            partial_sum(cnt, cnt + M, cnt + 1);
            cnt[0] = 0;
            for (int i = 0; i < M; i++) {
                _p[cnt[c[p[i]]]++] = p[i];
            }
            for (int i = 0; i < n; i++) p[i] = _p[i];
        }
    }
    ll s2 = (s + 1) / 2;
    int k = (n + 1) / 2;
    ll sm = 0;
    for0(i, k) {
        sm += a[p[i]];
        if (sm >= s2) {
            vector<int> ans;
            for (int f = 0; f < n; f++) {
                ans.push_back(p[f]);
            }
            return ans;
        }
    }
    for (int i = k - 1, r = n - 1; i >= 0; i--, r--) {
        if (sm - a[p[i]] + a[p[r]] >= s2) {
            for (int j = k; j < n; j++) {
                if (sm - a[p[i]] + a[p[j]] >= s2) {
                    vector<int> ans;
                    for (int f = 0; f < i; f++) ans.push_back(p[f]);
                    ans.push_back(p[j]);
                    for (int f = n - 1; f > r; f--) ans.push_back(p[f]);
                    for (int f = 0; f < n; f++) {
                        if (f < i || f > r || f == j) continue;
                        ans.push_back(p[f]);
                    }
                    return ans;
                }
            }
        } else {
            sm = sm - a[p[i]] + a[p[r]];
        }
    }
    assert(0);
}
