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

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

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

#define long int64_t

using namespace std;

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

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

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

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

        fill(cnt, cnt + p2, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[(a[p[i]] >> (K + K)) & (p2 - 1)];
        for (int i = 1; i < p2; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i)
            nw[--cnt[(a[p[i]] >> (K + K)) & (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
