#include "bits/stdc++.h"

using namespace std;

// #define int long long

vector<int> solve(vector<int> a) {
    int n = (int) a.size(), sm = 0;
    if (n == 1) {
        return {0};
    }
    vector<pair<int, int>> vec;
    for (int i = 0; i < n; i++) {
        vec.push_back({a[i], i});
        sm += a[i];
    }

    sort(vec.begin(), vec.end());

    int ans = 1e9;
    vector<int> vans;
    for (int cs = 0; cs < 2; cs++) {
        int del = (n >> 1) + cs;
        deque<int> dq;
        int sm1 = 0, ind = (n - 1);
        for (int i = 0; i < del; i++) {
            dq.push_back(vec[i].second);
            sm1 += vec[i].first;
        }
        while (sm1 < (sm & 1 ? ((sm >> 1) + 1) : (sm >> 1)) && ind >= del) {
            sm1 -= a[dq.front()];
            dq.pop_front();
            dq.push_back(vec[ind].second);
            sm1 += vec[ind].first;
            ind--;
        }
        if (sm1 >= (sm & 1 ? (sm >> 1) + 1 : (sm >> 1)) && ans > abs((n - del) - del)) {
            ans = abs((n - del) - del);
            for (auto i : dq)
                vans.push_back(i);
        }
    }
    vector<bool> used(n + 10);
    for (auto i : vans)
        used[i] = 1;
    for (int i = 0; i < n; i++)
        if (!used[i])
            vans.push_back(i);

    return vans;
}

// int32_t main() {

//     ios::sync_with_stdio(false);
//     cin.tie(nullptr); cout.tie(nullptr);

//     int T = 1;
//     cin >> T;
//     while (T--) {
//         int n;
//         cin >> n;
//         vector<int> a(n);
//         for (int i = 0; i < n; i++)
//             cin >> a[i];

//         int sm = 0;
//         vector<pair<int, int>> vec;
//         for (int i = 0; i < n; i++) {
//             vec.push_back({a[i], i});
//             sm += a[i];
//         }

//         sort(vec.begin(), vec.end());

//         int ans = 1e9;
//         vector<int> vans;
//         for (int cs = 0; cs < 2; cs++) {
//             int del = (n >> 1) + cs;
//             deque<int> dq;
//             int sm1 = 0, ind = (n - 1);
//             for (int i = 0; i < del; i++) {
//                 dq.push_back(vec[i].second);
//                 sm1 += vec[i].first;
//             }
//             while (sm1 < (sm & 1 ? ((sm >> 1) + 1) : (sm >> 1)) && ind >= del) {
//                 sm1 -= a[dq.front()];
//                 dq.pop_front();
//                 dq.push_back(vec[ind].second);
//                 sm1 += vec[ind].first;
//                 ind--;
//             }
//             if (sm1 >= (sm & 1 ? (sm >> 1) + 1 : (sm >> 1)) && ans > abs((n - del) - del)) {
//                 ans = abs((n - del) - del);
//                 for (auto i : dq)
//                     vans.push_back(i);
//             }
//         }
//         vector<bool> used(n + 10);
//         for (auto i : vans)
//             used[i] = 1;
//         for (int i = 0; i < n; i++)
//             if (!used[i])
//                 vans.push_back(i);

//         for (auto i : vans)
//             cout << a[i] << " ";
//         cout << '\n';
//     }

//     return 0;
// }