#include <bits/stdc++.h>

using namespace std;
int get (vector<int> ans, vector<int> A, long long s) {
    long long cr = 0;
    for (int i = 0; i < (int)ans.size(); ++i) {
        cr += A[ans[i]];
        if (cr * 2 >= s) return i + 1;
    }
}
mt19937_64 rng (time (0));
std::vector<int> solve(std::vector<int> A) {
    int n = (int)A.size();
    vector<int> b(n);
    long long sum = 0;
    iota (begin (b), end (b), 0);
    vector<int> c(n);
    sum = accumulate(begin (A), end (A), 0LL);

    if (!is_sorted(begin (A), end (A))) {
        sort (begin (b), end (b), [&](int le, int ri) {
            return A[le] < A[ri];
        });
    }
    for (int i = 0; i < n; ++i) c[i] = A[b[i]];
    int cl = 0;
    long long sl = 0;
    int cr = 0;
    long long sr = 0;
    for (int i = 0; i < n; ++i) {
        sl += c[i];
        ++cl;
        if (sl * 2 >= sum) break;
    }
    for (int i = n - 1; i >= 0; --i) {
        sr += c[i];
        ++cr;
        if (sr * 2 >= sum) break;
    }
    int Targ = (n + 1) / 2;
    Targ = min (Targ, cl);
    Targ = max (Targ, cr);
    vector<long long> P(n + 1);
    for (int i = 0; i < n; ++i) P[i] = (i == 0 ? 0 : P[i - 1]) + c[i];
    int cmid_val = 0;
    if (Targ == n) {
        vector<int> ans (n);
        iota (begin (ans), end (ans), 0);
        return ans;
    }
    for (int p_le = 0; p_le < Targ; ++p_le) {
        int p_ri = p_le + 1 + n - Targ + 1;
        cmid_val = max (cmid_val, p_le + 1);
        long long cs = P[p_le] + (p_ri == n ? 0 : P[n - 1] - (p_ri == 0 ? 0 : P[p_ri - 1]));
        if (cs * 2 >= sum) continue;
        while (cmid_val < p_ri && (cs + c[cmid_val]) * 2 < sum) {
            ++cmid_val;
        }
        if (cmid_val < p_ri) {
            vector<int> ans;

            for (int i = 0; i <= p_le; ++i) ans.push_back(b[i]);
            ans.push_back(b[cmid_val]);
            for (int i = p_ri; i < n; ++i) ans.push_back(b[i]);
            for (int i = p_le + 1; i < p_ri; ++i) {
                if (i == cmid_val) continue;
                ans.push_back(b[i]);
            }
            return ans;

        }
    }

    vector<int> res;
    --Targ;
    long long cs = 0;
    int pos_id = 0;
    for (int i = n - Targ; i < n; ++i) res.push_back(b[i]), cs += c[i];
    for (int i = 0; i < n - Targ; ++i) {
        if ((cs + c[i]) * 2 >= sum) {
            res.push_back(b[i]);
            pos_id = i;
            break;
        }
    }
    for (int i = 0; i < n - Targ; ++i) {
        if (i == pos_id) continue;
        res.push_back(b[i]);
    }


//    if (get (res, A, sum) != Targ) {
//        assert(0);
//    }
    return res;
}
#ifdef LOCAL
#include<iostream>
#include<vector>
using namespace std;
extern vector<int> solve(vector<int> A);
signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int t;
    cin >> t ;
//    t = 1;
    for (int test=1; test<=t; test++) {
        int n;
//        cin >> n ;
            n = 2e6;
//        n = rng() % 7 + 1;
        vector <int> a(n);
        for (int i=0; i<n; i++) {
//            cin >> a[i] ;
a[i] = i + 1;
//            a[i] = (rng () % 10) + 1;
        }

        for (auto ind : solve(a)) {
//            cout << ind << " ";
        }
        cout << (double)clock() / CLOCKS_PER_SEC << '\n';
        cout << endl ;
    }
    cout << endl ;
    return 0;
}

#endif // LOCAL
