#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

std::vector<int> solve(std::vector<int> A) {
    vector<pii> packs(A.size());
    ll sum = 0;
    int N = A.size();
    for (int i = 0; i < A.size(); i++) {
        packs[i] = {A[i], i};
        sum += A[i];
    }
    sort(packs.begin(), packs.end());
    ll M = (sum + 1)/2;
    ll mid_sum = 0;
    vector<int> ans(N);
    vector<int> part(N);
    for (int i = 0; i < (N - 1)/2; i++) {
        int idx = packs[i].second;
        ans[idx] = 1;
        mid_sum += packs[i].first;
    }
    ans[packs[(N - 1)].second] = 1;
    mid_sum += packs[(N - 1)].first;
    for (int i = (N - 1)/2; i < N - 1; i++) {
        int idx = packs[i].second;
        ans[idx] = 2;
    }
    int last = 0, minus = 2, last_idx = packs[N - 1].second;
    while (mid_sum < M) {
        int cur = N - minus;
        int idx = packs[cur].second;
        ans[idx] = 1;
        mid_sum += A[idx];
        int idx2 = packs[last].second;
        ans[idx2] = 2;
        mid_sum -= A[idx2];
        //cout << mid_sum << endl;
        last++;
        minus++;
    }
    vector<int> divide;
    for (int i = 0; i < N; i++) {
        if (i != last_idx && ans[i] == 1) divide.push_back(i);
    }    
    divide.push_back(last_idx);
    for (int i = 0; i < N; i++) {
        if (ans[i] == 2) divide.push_back(i);
    }
    return divide;
}

// int main () {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     int t;
//     cin >> t ;
//     for (int test=1; test<=t; test++) {
//         int n;
//         cin >> n ;
//         vector <int> a(n);
//         for (int i=0; i<n; i++) {
//             cin >> a[i] ;
//         }

//         for (auto ind : solve(a)) {
//             cout << ind << " ";
//         }
//         cout << endl ;
//     }
//     cout << endl ;
//     return 0;
// }