#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;

    vector<ll> pref(n);
    for (int i=0; i<n; i++)
        pref[i] = b[i].first + (i ? pref[i-1] : 0);

    auto query = [&](int l, int r) {
        if (l > r) swap(l, r);
        return pref[r] - (l ? pref[l-1] : 0);
    };

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

    int j = 0;
    array<int, 3> opt = { n+1, -1, -1 };
    for (int i=0; i<n; i++) {
        while (j+1 <= i && 2ll*query(j, i) >= tot && 2ll*query(j+1, i) >= tot) j++;

        if (2ll*query(j, i) >= tot) {
            int len = i-j+1;
            if (abs(2*len - n) < opt[0]) {
                opt[0] = abs(2*len-n);
                opt[1] = j;
                opt[2] = i;
            }
        }
    }

    j = n-1;
    for (int i=n-1; i>=0; i--) {
        while (j-1 >= i && 2ll*query(i, j) >= tot && 2ll*query(i, j-1) >= tot) j--;

        if (2ll*query(i, j) >= tot) {
            int len = j-i+1;
            if (abs(2*len-n) < opt[0]) {
                opt[0] = abs(2*len-n);
                opt[1] = j;
                opt[2] = i;
            }
        }
    }

    if (opt[1] <= opt[2] && opt[0] <= n) {
        for (int i=opt[1]; i<=opt[2]; i++)
            ans.push_back(b[i].second);
        for (int i=0; i<n; i++)
            if (i < opt[1] || i > opt[2])
                ans.push_back(b[i].second);
    } else if (opt[0] <= n) {
        for (int i=opt[2]; i>=opt[1]; i--)
            ans.push_back(b[i].second);
        for (int i=0; i<n; i++)
            if (i < opt[1] || i > opt[2])
                ans.push_back(b[i].second);
    }

    sum = 0;
    cur = opt[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;
        }
    }

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