#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], c[N], p[N];

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

std::vector<int> solve(std::vector<int> _a) {
    int n = sz(_a);
    for (int i = 0; i < n; i++) a[i] = _a[i], p[i] = i;
    int k = (n + 1) / 2;
    ll s = accumulate(a, a + n, 0ll);
    ll s2 = (s + 1) / 2;
    for (int i = 0; i < k; i++) {
        if (a[p[i]] > a[p[n - 1 - i]]) {
            swap(p[i], p[n - 1 - i]);
        }
    }
    ll sm = 0;
    for (int i = 0; i < k; i++) sm += a[p[i]];
    if (sm >= s2) {
        vector<int> ans;
        for (int f = 0; f < n; f++) {
            ans.push_back(p[f]);
        }
        return ans;
    }
    for (int i = 0, r = n - 1; 1; i++, r--) {
        if (sm - a[p[i]] + a[p[r]] >= s2) {
            swap(p[i], p[r]);
            int it = 0;
            for (int f = 0; f < k; f++) {
                if (f == i) continue;
                _a[it++] = p[f];
            }
            _a[it++] = p[i];
            for (int f = k; f < n; f++) {
                _a[it++] = p[f];
            }
            return _a;
        } else {
            sm = sm - a[p[i]] + a[p[r]];
            swap(p[i], p[r]);
        }
    }
    assert(0);
}
