#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> v(n);
    for (int i = 0; i < n; i++) v[i] = i;
    sort(all(v), comp);
    
    ll sum1 = 0, sum2 = 0;
    vector<int> vec1, vec2;
    for (int i : v) {
        if (sum1 < sum2) {
            vec1.pb(i); sum1 += arr[i];
        } else {
            vec2.pb(i); sum2 += arr[i];
        }
    }

    // cout << abs(sum1 - sum2) << '\n';

    for (int i : vec2) vec1.pb(i);
    return vec1;
}

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