#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> solve(vector<int> a)
{
    ll sm = 0;
    for (int x : a) sm += x;
    sm = (sm/2) + (sm&1);
    int n = a.size();
    int bst = n;
    vector<int> fr;
    vector<int> t;

    for (int i = 1; i < (1<<n); i++)
    {
        t.clear();
        for (int j = 0; j < n; j++) if ((i>>j)&1) t.push_back(j);

        ll s = 0;
        ll b = -1;
        for (int x : t) 
        {
            s += x;
            b = max<ll>(b, x);
        }
        if (s >= sm && (s-b) < sm) if (abs((n - __builtin_popcount(i)) - __builtin_popcount(i)) < n)
        {
            bst = abs((n - __builtin_popcount(i)) - __builtin_popcount(i));
            fr = t;
        }
    }

    vector<bool> in(n);
    vector<int> ans = fr;
    swap(ans.back(), *max_element(ans.begin(), ans.end()));
    for (int x : ans) in[x] = true;
    for (int i = 0; i < n; i++) 
    {
        if (!in[i]) ans.push_back(i);
    }

    return ans;
} 


// int dif(vector<int> v)
// {
//     int n = v.size();
//     ll s = 0;
//     for (int x : v) s += x;
//     s = (s/2) + (s&1);
//     ll x = 0;
//     for (int i = 0; i < n; i++)
//     {
//         x += v[i];
//         if (x >= s) 
//         {
//             i++;
//             return abs((n - i) - i);
//         }
//     }
//     return n;
// }


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

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