#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 10000009;

int b[N];

bool cmp(int i, int j) { return b[i] < b[j]; }

vector < int > solve(vector < int > ab) {
    int n = (int)ab.size();
    for (int i = 0; i < n; i++) b[i] = ab[i];

    vector < int > a(n), num(n);
    for (int i = 0; i < n; i++) num[i] = i;
    sort(num.begin(), num.end(), cmp);
    for (int i = 0; i < n; i++) a[i] = b[num[i]];

    ll s = 0;
    for (auto x : a) s += x;

    ll crr = 0;
    int mn = 0, mx = 0;

    for (int i = 0; i < n; i++) {
        mx++, crr += a[i];
        if (crr * 2ll >= s) break;
    }

    crr = 0;
    for (int i = n - 1; i >= 0; i--) {
        mn++, crr += a[i];
        if (crr * 2ll >= s) break;
    }

    int opt = (n + 1) / 2;
    opt = max(mn, min(mx, opt));

    if (opt == n) {
        vector < int > res(n);
        for (int i = 0; i < n; i++) res[i] = i;
        return res;
    }

    crr = 0;
    vector < ll > p(n);
    for (int i = 0; i < n; i++) { crr += a[i]; p[i] = crr; }

    int lg = 0;

    for (int l = 0; l < opt; l++) {
        int r = opt - l - 1;
        ll base = 0;
        if (l) base += p[l - 1];
        if (r) base += (s - (n - r - 1 >= 0 ? p[n - r - 1] : 0ll));

        while (lg < n && (base + a[lg]) * 2ll < s) lg++;
        lg = max(lg, l);
        if (lg >= n) break;

        if (lg < n - r) {
            ll val = a[lg] + base;
            ll val1 = val;
            if (r) val1 -= a[n - 1];
            else val1 -= a[lg];

            if (val * 2ll >= s && val1 * 2ll < s) {
                for (int i = 0; i < l; i++) a[i] = num[i];
                a[l] = num[lg];
                for (int i = n - r; i < n; i++) a[(i - n + r) + l + 1] = num[i];
                int k = l + r + 1;
                for (int i = l; i < lg; i++) a[k + i - l] = num[i];
                k = l + r + 1 + (lg - l);
                for (int i = lg + 1; i < n - r; i++) a[k + i - lg - 1] = num[i];
                return a;
            }
        }
    }

    exit(1);
}