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

#define ll long long
#define pb push_back
#define all(x) (x).begin(),(x).end()

vector<int> arr;
bool comp(int x, int y) {
    return arr[x] < arr[y];
}
std::vector<int> solve(std::vector<int> _arr) {
    arr = _arr;
    int n = arr.size(); vector<int> ord(n);
    for (int i = 0; i < n; i++) ord[i] = i;
    sort(all(ord), comp);

    ll mn = 0, mx = 0, s = 0;
    for (int i : arr) s += i;

    int best = 0;
    for (int i = 1; i <= n; i++) {
        mn += arr[ord[i - 1]]; mx += arr[ord[n - i]];
        if (mn <= s / 2 && s / 2 <= mx && abs(n - 2 * i) < abs(n - 2 * best)) best = i;
    }

    int pos[best + 1]; ll curs = 0; pos[best] = n;
    for (int i = 0; i < best; i++) pos[i] = i, curs += arr[ord[i]];
    for (int i = best - 1; i >= 0 && curs < s / 2; i--) {
        for (int j = best; j < pos[i + 1]; j++) {
            if (curs - arr[ord[pos[i]]] + arr[ord[j]] >= s / 2) {
                pos[i] = j; curs = curs - arr[ord[pos[i]]] + arr[ord[j]]; break;
            }
        }

        if (curs < s / 2)  {
            curs = curs - arr[ord[pos[i]]] + arr[ord[n - (best - i)]];
            pos[i] = n - (best - i);
        }
    }

    vector<int> ans; bool isb[n]{};
    for (int i = 0; i < best; i++) {
        ans.pb(ord[pos[i]]); isb[pos[i]] = 1;
    }

    for (int i = 0; i < n; i++) {
        if (!isb[i]) ans.pb(ord[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;
// }
