#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;

vector <int> v;
int a2[N], p[N], nw[N], cnt[N];

vector <int> solve(vector <int> a) {
    int n = a.size();
    iota(p, p + n, 0);
    if (n <= 14)
        sort(p, p + n, [&](int i, int j) {
            return a[i] < a[j];
        });
    else {
        int k = log2(n), pp = (1 << k);
        int mx = 1e9;
        copy(a.begin(), a.end(), a2);
        while (mx > 0) {
            mx >>= k;
            fill(cnt, cnt + pp, 0);
            for (int i = 0; i < n; ++i)
                ++cnt[(a2[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[a2[p[i]] & (pp - 1)]++] = p[i];
                a2[p[i]] >>= k;
            }
            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
