#include "partition.h"
#include "bits/stdc++.h"

#define pb push_back
#define ll long long

using namespace std;

const ll inf = 1e9 + 7;

vector<int> solve(vector<int> a) {
    int n = a.size();

    vector<int> p(n);

    iota(p.begin(), p.end(), 0);

    sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });

    sort(a.begin(), a.end(), [&](int i, int j) { return i < j; });

    ll s = accumulate(a.begin(), a.end(), 0ll), oksum = 0;

    int ans = inf, indi, indj;

    for (int i = 0; i < n; i++) {
        int sum = (oksum += a[i]);

        for (int j = 0; j <= i; j++) {
            int x;

            if (!j) {
                x = a[i];
            }
            else {
                x = a[n - 1];
            }

            if (sum * 2 >= s && (sum - x) * 2 < s) {
                if (ans > abs(i + 1 - (n - i - 1))) {
                    ans = abs(i + 1 - (n - i - 1));

                    indi = i, indj = j;
                }
            }

            sum -= a[i - j];
            sum += a[n - j - 1];
        }
    }

    vector<int> ret;

    for (int i = 0; i <= indi - indj; i++) {
        ret.pb(p[i]);
    }

    for (int i = n - 1; i >= n - indj; i--) {
        ret.pb(p[i]);
    }

    for (int i = indi - indj + 1; i < n - indj; i++) {
        ret.pb(p[i]);
    }

    return ret;
}
/*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;
}*/
