#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 = 15, M = 1 << C;

int a[N], a1[N], c[N], p[N];

#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] = a1[i] = _a[i];
    ll s = accumulate(a, a + n, 0ll);
    iota(p, p + n, 0);
    ll s2 = (s + 1) / 2;
    int k = (n + 1) / 2;
    nth_element(a1, a1 + k - 1, a1 + n);
    int med = a1[k - 1];
    int c0 = 0, c1 = 0, c2 = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < med) c0++;
        else if (a[i] == med) c1++;
        else c2++;
    }
    c2 = c0 + c1;
    c1 = c0;
    c0 = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < med) {
            p[c0++] = i;
        } else if (a[i] == med) {
            p[c1++] = i;
        } else {
            p[c2++] = i;
        }
    }
    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 = 0, r = n - 1; i < k; i++, r--) {
        if (sm - a[p[i]] + a[p[r]] >= s2) {
            if (sm - a[p[i]] + a[p[r]] >= s2) {
                vector<int> ans;
                for (int f = i + 1; f < k; f++) ans.push_back(p[f]);
                ans.push_back(p[r]);
                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 == r) continue;
                    ans.push_back(p[f]);
                }
                return ans;
            }
        } else {
            sm = sm - a[p[i]] + a[p[r]];
        }
    }
    assert(0);
}
