#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())

using namespace std;
const int N = 2e6;
int p[N];
pair < int, int > A[N];

vector < int > solve (vector < int > a) {
    int n = sz(a);
    ll S = 0;
    for (int i = 0; i < n; ++i) {
        p[i] = i;
        S += a[i];
    }

    nth_element(p, p + (n + 1) / 2 - 1, p + n, [&](int i, int j) {
        return a[i] < a[j];
    });
    ll si = 0;
    S = (S + 1) / 2;
    int c = 0, j = n - 1;
    while (si < S)
        si += a[p[j--]];
    for (int i = -1; i < n; ++i) {
        if (i >= 0) {
            si += a[p[i]];
            a[c++] = p[i];
        }
        if (j + 1 < n && si - a[p[j + 1]] >= S)
            si -= a[p[++j]];
        if (i + 1 + n - 1 - j >= (n + 1) / 2) {
            for (int k = n - 1; k > j; --k)
                a[c++] = p[k];
            for (int k = i + 1; k <= j; ++k)
                a[c++] = p[k];
            return a;
        }
    }
    return a;
}
//
//signed main () {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    int test = 1;
//    vector < int > a;
//    cin >> test;
//    while (test--) {
//        int n;
//        cin >> n;
//        a.resize(n);
//        for (int i = 0; i < n; ++i)
//            cin >> a[i];
//        a = solve(a);
//        for (int x : a)
//            cout << x << " ";
//        cout << "\n";
//    }
//}
