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

#define f first
#define s second
#define pb push_back
#define elif else if
#define nl '\n'

#pragma GCC optimize("O3,unroll-loops")
#pragma target("avx2,bmi,bmi2,pop_cnt,lz_cnt")

#define long int64_t

using namespace std;

const int N = 2e6 + 9, K = 10, pp = (1 << K), K2 = 15, p2 = (1 << K2);

vector <int> v;
int p[N], nw[N], cnt[p2 + 9];

vector <int> solve(vector <int> a) {
    int n = a.size();
    iota(p, p + n, 0);
    if (n <= 400)
        sort(p, p + n, [&](int i, int j) {
            return a[i] < a[j];
        });
    elif (6 * n + 3 * pp <= 4 * n + 2 * p2) {
        fill(cnt, cnt + pp, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[(a[i] & (pp - 1)) + 1];
        for (int i = 1; i < pp; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; ++i)
            nw[cnt[a[i] & (pp - 1)]++] = i;
        copy(nw, nw + n, p);

        fill(cnt, cnt + pp, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[((a[i] >> K) & (pp - 1)) + 1];
        for (int i = 1; i < pp; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; ++i)
            nw[cnt[(a[p[i]] >> K) & (pp - 1)]++] = p[i];
        copy(nw, nw + n, p);

        fill(cnt, cnt + pp, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[((a[i] >> (K + K)) & (pp - 1)) + 1];
        for (int i = 1; i < pp; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; ++i)
            nw[cnt[(a[p[i]] >> (K + K)) & (pp - 1)]++] = p[i];
        copy(nw, nw + n, p);
    }
    else {
        fill(cnt, cnt + p2, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[(a[i] & (p2 - 1)) + 1];
        for (int i = 1; i < p2; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; ++i)
            nw[cnt[a[i] & (p2 - 1)]++] = i;
        copy(nw, nw + n, p);

        fill(cnt, cnt + p2, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[((a[i] >> K2) & (p2 - 1)) + 1];
        for (int i = 1; i < p2; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; ++i)
            nw[cnt[(a[p[i]] >> K2) & (p2 - 1)]++] = p[i];
        copy(nw, nw + n, p);
    }
    long sum = 0;
    for (int i = 0; i < n; ++i)
        sum += a[i];
    long s = 0;
    int i = 0;
    while (s < (sum + 1) / 2) {
        s += a[p[i]];
        ++i;
    }
    int j = n - 1, ans = abs(n - (i + (n - 1 - j)) * 2), l = i, r = 0;
    while (i > 0) {
        --i;
        s -= a[p[i]];
        if (s < (sum + 1) / 2) {
            s += a[p[j]];
            --j;
        }
        if (abs(n - (i + (n - 1 - j)) * 2) < ans) {
            ans = abs(n - (i + (n - 1 - j)) * 2);
            l = i;
            r = n - 1 - j;
        }
    }
    v.clear();
    for (int i = 0; i < l; ++i)
        v.pb(p[i]);
    for (int i = n - r; i < n; ++i)
        v.pb(p[i]);
    for (int i = l; i < n - r; ++i)
        v.pb(p[i]);
    return v;
}

#undef long
