#include<bits/stdc++.h>

#pragma GCC optimize("O3")

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

using namespace std;
const int N = 2e6;
vector < 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) {
        A[i] = {a[i], i};
        S += a[i];
    }
    auto m = A.begin() + (n + 1) / 2 - 1;
    nth_element(A.begin(), m, A.begin() + n);
    int ans = n + 1;
    ll si = 0;
    S = (S + 1) / 2;
    int l, r;
    int j = n - 1;
    while (si < S)
        si += A[j--].first;
    for (int i = -1; i < n; ++i) {
        if (!ans) break;
        if (i >= 0) si += A[i].first;
        if (j + 1 < n && si - A[j + 1].first >= S)
            si -= A[++j].first;
        if (si < S) continue;
        int fir = i + 1 + n - 1 - j, sec = n - fir;
        if (i >= (n + 1) / 2) break;
        if (ans > abs(fir - sec)) {
            ans = min(ans, abs(fir - sec));
            l = i, r = j + 1;
        }
    }
    int c = 0;
    for (int i = 0; i <= l; ++i)
        a[c++] = A[i].second;
    for (int i = n - 1; i >= r; --i)
        a[c++] = A[i].second;
    for (int i = l + 1; i < min(n, r); ++i)
        a[c++] = A[i].second;
//    cout << "\n";
//    for (int i = 0; i < n; ++i)
//        cout << A[i].first << " ";
//    cout << "\n";
//    cout << l << " " << r << "\n";
    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";
//    }
//}
