#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define sc second
#define ll long long
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int maxN = 2 * 1e5;

int get(ll x) {
    int cnt = 0;
    while (x % 2 == 0) {
        cnt++; x /= 2;
    }
    return cnt;
}
std::vector<int> solve(std::vector<int> arr) {
    int n = arr.size(); ll s = 0;
    for (int i : arr) s += i;

    int best = n, msk;
    for (int j = 0; j < (1 << n); j++) {
        ll cur = 0; int mx = 0;
        for (int i = 0; i < n; i++) {
            if ((j >> i) % 2 == 0) continue;
            cur += arr[i]; mx = max(mx, arr[i]);
        }

        if (cur >= s / 2 && cur - mx < s / 2) {
            int x = __builtin_popcount(j);
            if (abs(n - 2 * x) < best) {
                best = abs(n - 2 * x); msk = j;
            }
        }
    }

    bool used[n]{};
    int mx = 0, mxp = 0;
    for (int i = 0; i < n; i++) {
        if ((msk >> i) % 2 == 0) continue;
        used[i] = 1;
        if (mx < arr[i]) {
            mx = arr[i]; mxp = i;
        }
    }

    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if ((msk >> i) % 2 == 0) continue;
        if (i == mxp) continue;
        ans.pb(i);
    }

    ans.pb(mxp);
    for (int i = 0; i < n; i++) {
        if (!used[i]) ans.pb(i);
    }
    return ans;
}


// 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;
// }
