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

using namespace std;

#define for0(i, n) for (ll i = 0; i < n; i++)
#define for1(i, n) for (ll i = 1; i < n; i++)
#define rfor0(i, n) for (ll i = n - 1; i >= 0; i--)
#define be(x) x.begin()
#define en(x) x.end()
#define all(x) be(x), en(x)
#define sz(x) x.size()
#define pb push_back
#define con continue
#define ret return

typedef long long ll;
typedef vector<ll> vll;

const int N = 2e6 + 5;

int a[N];

#pragma GCC optimize("O3")
#pragma GCC target("avx2,sse4")

std::vector<int> solve(std::vector<int> _a) {
    bool F = 0;
    int n = sz(_a);
    for (int i = 0; i < n; i++) a[i] = _a[i];
    link:
    int k = (n + 1) / 2;
    ll s = 0, sm = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
        sm += a[i] * (i < k);
    }
    ll s2 = (s + 1) / 2;
    if (sm >= s2) {
        if (!F) {
            F = 1;
            reverse(a, a + n);
            goto link;
        }
        vector<int> ans;
        for (int f = 0; f < n; f++) {
            ans.push_back(f);
        }
        return ans;
    }
    for (int i = 0, r = n - 1; 1; i++, r--) {
        if (sm - a[i] + a[r] >= s2) {
            swap(a[i], a[r]);
            int it = 0;
            for (int f = 0; f < k; f++) {
                if (f == i) continue;
                _a[it++] = f;
            }
            _a[it++] = i;
            for (int f = k; f < n; f++) {
                _a[it++] = f;
            }
            if (F) for (auto &x : _a) x = n - 1 - x;
            return _a;
        } else {
            sm = sm - a[i] + a[r];
            swap(a[i], a[r]);
        }
    }
    assert(0);
}
