#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector < int > solve(vector < int > ab) {
    int n = (int)ab.size();

    vector < array < int , 2 > > a(n);
    for (int i = 0; i < n; i++) a[i] = {ab[i], i};
    sort(a.begin(), a.end());

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

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

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

    crr = 0;
    for (int i = n - 1; i >= 0; i--) {
        mn++, crr += a[i][0];
        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][0]; p[i] = crr; }

    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));

        int lg = l, rg = n - r - 1;

        while (lg < rg) {
            int mid = (lg + rg) >> 1;
            ll val = a[mid][0] + base;
            if (val * 2ll >= s) rg = mid;
            else lg = mid + 1;
        }

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

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

    exit(1);
}