#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

std::vector<int> solve(std::vector<int> a) {
    vector<int> ans;
    int n = a.size();
    int cur = n+1;

    if (n == 1) return vector<int>{ 0 };

    if (n == 2) {
        if (a[0] >= a[1]) return { 0, 1 };
        return { 1, 0 };
    }

    vector<pii> b;
    for (int i=0; i<n; i++)
        b.push_back({ a[i], i });

    sort(b.begin(), b.end());

    ll tot = 0;
    for (int x : a) tot += x;

    ll sum = 0;
    for (int i=0; i<n; i++) {
        sum += b[i].first;
        if (2ll*sum >= tot) break;

        ll sum2 = sum;
        for (int j=n-1; j>=max(0, i+1); j--) {
            sum2 += b[j].first;

            if (2ll*sum2 >= tot) {
                int len = i + 1 + n - j;
                if (abs(len - (n - len)) < cur) {
                    cur = abs(len - (n - len));
                    ans.clear();

                    for (int k=0; k<=i; k++)
                        ans.push_back(b[k].second);
                    for (int k=n-1; k>=j; k--)
                        ans.push_back(b[k].second);
                    for (int k=i+1; k<j; k++)
                        ans.push_back(b[k].second);
                }
                break;
            }
        }
    }

    sum = 0;
    for (int i=0; i+1<n; i++) {
        sum += b[i].first;

        if (2ll * (sum + b[n-1].first) >= tot) {
            int len = i + 2;
            if (abs(2*len - n) < cur) {
                cur = abs(2*len-n);
                ans.clear();
                for (int j=0; j<=i; j++) ans.push_back(b[j].second);
                ans.push_back(b[n-1].second);
                for (int j=i+1; j+1<n; j++) ans.push_back(b[j].second);
            }
            break;
        }
    }

    for (int i=0; i<n; i++) {
        ll sum = 0;
        for (int j=i; j<n; j++) {
            sum += b[j].first;
            if (2ll*sum >= tot) {
                int len = j-i+1;
                if (abs(len - (n - len)) < cur) {
                    cur = abs(len - (n - len));
                    ans.clear();
                    for (int k=i; k<=j; k++)
                        ans.push_back(b[k].second);

                    for (int k=0; k<n; k++) {
                        if (k < i || k > j)
                            ans.push_back(b[k].second);
                    }
                }
                break;
            }
        }
    }

    // for (int j=n-1; j>=0; j--) {
    //     ll sum = 0;
    //     for (int i=j; i>=0; i--) {
    //         sum += b[i].first;
    //         if (2ll*sum >= tot) {
    //             int len = j-i+1;
    //             if (abs(len - (n - len)) < cur) {
    //                 cur = abs(len - (n - len));
    //                 ans.clear();
    //                 for (int k=j; k>=i; k--)
    //                     ans.push_back(b[k].second);
    //
    //                 for (int k=0; k<n; k++) {
    //                     if (k < i || k > j)
    //                         ans.push_back(b[k].second);
    //                 }
    //             }
    //             break;
    //         }
    //     }
    // }

    assert(ans.size() == n);
    return ans;
}
