#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) {
    int n = sz(_a);
    for (int i = 0; i < n; i++) a[i] = _a[i];
    int k = (n + 1) / 2;
    ll s = accumulate(a, a + n, 0ll);
    ll s2 = (s + 1) / 2;
    ll sm = 0;
    iota(all(_a), 0);
    for (int i = 0; i < k; i++) {
        if (a[i] > a[n - 1 - i]) swap(_a[i], _a[n - 1 - i]);
        sm += min(a[i], a[n - 1 - i]);
    }
    int i = 0;
    while (sm < s2) swap(_a[i], _a[n - 1 - i]), sm += max(a[i], a[n - 1 - i]) - min(a[i], a[n - 1 - i]), i++;
    if (i) swap(_a[i - 1], _a[k - 1]);
    return _a;
}
