#include<iostream>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
#include "partition.h"

using ll = long long;
const int N = 2e6;
std::pair<int, int> b[N];


std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    if (n == 1) return {0};
    ll S = std::accumulate(a.begin(), a.end(), 0ll);
    int mx = std::max_element(a.begin(), a.end()) - a.begin();
    int sz = 0;
    for (int i = 0; i < n; ++i) {
        if (i != mx) b[sz++] = {a[i], i};
    }
    std::nth_element(b, b + (n - 1) / 2, b + n - 1);
    int L = 0, R = (n - 1) / 2 + 1;
    ll s = 0;
    while (R - L > 1) {
        int M = (L + R) / 2;
        nth_element(b + L, b + M, b + R);
        ll ns = s;
        for (int i = L; i < M; ++i) ns += b[i].first;
        if (ns <= (S + 1) / 2) {
            s = ns;
            L = M;
        } else {
            R = M;
        }
    }
    int cnt = L;
    L = 0, R = n - 1 - cnt;
    while (R < n - 1) {
        ll ns = s + b[L].first - b[R].first;
        if (ns <= (S - 1) / 2) {
            s = ns;
            ++L, ++R;
        } else {
            break;
        }
    }
    std::vector<int> ret(n);
    int c = 0;
    for (int i = 0; i < L; ++i) ret[c++] = b[i].second;
    for (int i = R; i < n - 1; ++i) ret[c++] = b[i].second;
    ret[c++] = mx;
    for (int i = L; i < R; ++i) ret[c++] = b[i].second;
    return ret;
}