#include<bits/stdc++.h>

#pragma GCC optimize("O3")

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

using namespace std;

const int N = 2e6;
const int C = 31623;
const int LUCK = 1.5e6;
pair < int, int > A[N];
vector < int > v[C];

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];
    }
    if (n < LUCK) {
        sort(A, A + n);
    } else {
        vector < int > p(n);
        ll S = 0;
        iota(all(p), 0);
        for (int i = 0; i < n; ++i)
            v[a[i] % C].pb(i);
        int pp = 0;
        for (int i = 0; i < C; ++i) {
            for (int x : v[i])
                p[pp++] = x;
            v[i].clear();
        }
        for (int i = 0; i < n; ++i) {
            v[a[p[i]] / C].pb(p[i]);
        }
        pp = 0;
        for (int i = 0; i < C; ++i) {
            for (int x : v[i])
                p[pp++] = x;
            v[i].clear();
        }

        for (int i = 0; i < n; ++i) {
            A[i] = {a[p[i]], p[i]};
        }
    }
//    sort(A, A + 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 > n / 2 && ans < n / 2) break;
        if (i >= 0) si += A[i].first;
//        ll x = si;
        if (j + 1 < n && si - A[j + 1].first >= 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;
//    cout << "\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";
//    }
//}
