#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 sum = 0;

    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 tot = 0;
    for (int x : a) tot += x;

    array<int, 3> opt = { n+1, -1, -1 };

    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) < opt[0]) {
                opt = { abs(2*len-n), i, -1 };
            }
            break;
        }
    }

    int j = n-1;
    sum = 0;
    for (int i=n-1; i>=0; i--) {
        while (j-1 >= i && sum*2 >= tot && (sum-b[j].first)*2) j--;
        int len = j-i+1;
        if (2ll*sum >= tot && abs(2*len-n) < opt[0]) {
            opt = { abs(2*len-n), i, j };
        }
    }

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

    return ans;
}
