#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    vector<pair<int, int>> q;
    for (int k = 1; k <= n; ++k) {
        int f1 = k, f2 = n - k;
        int d = abs(f1 - f2);
        q.push_back({d, k});
    }
    vector<int> ans;
    sort(q.begin(), q.end());
    long long s = 0;
    for (auto i : A) s += i;
    vector<pair<long long, int>> f;
    for (int i = 0; i < n; ++i) {
        f.push_back({A[i], i});
    }
    sort(f.begin(), f.end());
    vector<long long> pref(n);
    vector<bool> can;
    long long ss = 0;
    for (int i = 0; i < n; ++i) {
        if (i - 1 >= 0) {
            pref[i] = pref[i - 1];
        }
        pref[i] += f[i].first;
        ss += f[i].first;
        if (2 * ss < s || 2 * (ss - f[i].first) < s) can.push_back(true);
        else can.push_back(false);
    }
    for (auto [d, k] : q) {
        long long sum = pref[k - 1];
        if (2 * sum < s) {
            int l = 1, r = min(k, n - k);
            auto check = [&](int del) {
                int res = -pref[del - 1];
                int l = n - del, r = n - 1;
                res += pref[r];
                if (l > 0) res -= pref[l - 1];
                return 2 * (sum + res) >= s;
            };
            while (true) {
                if (l >= r) break;
                int mid = (l + r) >> 1;
                if (check(mid)) r = mid;
                else l = mid + 1;
            }
            vector<bool> used(n);
            for (int i = l; i < k; ++i) ans.push_back(f[i].second);
            for (int i = n - l; i < n; ++i) ans.push_back(f[i].second);
            for (auto &i : ans) used[i] = true;
            for (int i = 0; i < n; ++i) {
                if (!used[i]) ans.push_back(i);
            }
           /* set<pair<int, int>> q1, q2;
            for (int j = 0; j < k; ++j) {
                q1.insert(f[j]);
            }
            for (int j = k; j < n; ++j) {
                q2.insert(f[j]);
            }
            while (true) {
                auto [v1, i1] = *q1.begin();
                auto [v2, i2] = *q2.rbegin();
                if (v1 >= v2) break;
                sum -= v1, sum += v2;
                q1.erase({v1, i1}), q2.erase({v2, i2});
                q1.insert({v2, i2}), q2.insert({v1, i1});
                if (2 * sum >= s) break;
            }
            for (auto [v1, i1] : q1) ans.push_back(i1);
            for (auto [v2, i2] : q2) ans.push_back(i2);*/
            return ans;
        } else {
            if (can[k - 1]) {
                for (auto [val, idx] : f) ans.push_back(idx);
                return ans;
            }
        }
        //cout << d << ' '<< k << endl;
    }
    return ans;
}
/*signed main() {
    for (auto i : solve({5, 6, 6 ,3 ,1 ,1, 4 ,4 ,3})) {
        cout << i << endl;
    }
    return 0;
}*/
