#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;
pair < int, int > A[N];

vector < int > solve (vector < int > a) {
    int n = sz(a);


//    vector < int > p(n);
    ll S = 0;
//    for (int i = 0; i < n; ++i) S += a[i];
//    iota(all(p), 0);
//    sort(all(p), [&](int li, int ri) {
//        return a[li] < a[ri];
//    });
    for (int i = 0; i < n; ++i) {
        A[i] = {a[i], i};
        S += a[i];
    }
    int ans = n + 1;
    ll si = 0;
    S = (S + 1) / 2;
//    int opt = 0;
    int l, r;
    int j = n - 1;
    for (int i = -1; i < n; ++i) {
        if (!ans) break;
        if (i >= 0) si += A[i].first;
//        ll x = si;
        while (j + 1 < n && si > S) {
            si -= A[++j].first;
        }
        while (si < S) {
            si += A[j--].first;
        }
        int fir = i + 1 + n - 1 - j, sec = n - fir;
        if (ans > abs(fir - sec)) {
            ans = min(ans, abs(fir - sec));
            l = i, r = j + 1;
        }
    }
//    cout << ans << " " << l << " " << r << "\n";
    int c = 0;
    for (int i = 0; i <= l; ++i)
        a[c++] = A[i].second;
    for (int i = r; i < n; ++i)
        a[c++] = A[i].second;
    for (int i = l + 1; i < min(n, r); ++i)
        a[c++] = A[i].second;
    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 = slv(a);
//        for (int x : a)
//            cout << x << " ";
//        cout << "\n";
//    }
//}
