#include "bits/stdc++.h"
#include "partition.h"
// #include "grader.cpp"
using namespace std;


#define N 3000005
#define ll long long

const int inf = INT_MAX;

ll n, ans, S = 0;
vector <int> a, b, c, d;

void FF(int x,ll sm,int cnt) {
    if(sm * 2 >= S) {
        int l = cnt;
        int r = n - cnt;
        if(ans > abs(r - l)) {
            a.clear();
            ans = abs(r - l);
            for(int i = 0; i < n; i++) {
                c[i] = b[i];
                if(b[i]) a.push_back(i);
            }
        }
        return;
    }
    if(x == n) return;
    b[x] = 1;
    FF(x + 1, sm + d[x], cnt + 1);
    b[x] = 0;
    FF(x + 1, sm, cnt);
}

vector<int> solve(vector<int> A) {
    n = (int)A.size();
    d.clear();
    a.clear();
    S = 0;
    for(int i = 0; i < n; i++) {
        d.push_back(i);
        S += A[i];
        a.push_back(i);
    }
    ans = n + 1;
    sort(d.begin(),d.end());
    do{
        int a1 = 0, p = n;
        for(int i = 0; i <n; i++) {
            a1 += A[d[i]];
            if(a1 * 2 >= S) {
                p = i;
                break;
            }
        }
        int r = n - p;
        if(ans > abs(r - p)) {
            ans = abs(r - p);
            for(int i = 0; i < n; i++) {
                a[i] = d[i];
            }
        }
    }while(next_permutation(d.begin(),d.end()));
    // a.clear();
    // c.clear();
    // b.clear();
    // d.clear();
    // S = 0;
    // for(int i = 0; i < n; i++) {
    //     d.push_back(A[i]);
    //     S += A[i];
    //     b.push_back(0);
    //     c.push_back(0);
    // }

    // ans = n + 1;

    // FF(0, 0, 0);
    
    // for(int i = 0; i < n; i++) {
    //     if(!c[i]) a.push_back(i);
    // }
    // swap(A[n - 1], A[n / 2]);
    return a;
}