#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());
    for (auto [d, k] : q) {
        long long sum = 0;
        for (int j = 0; j < k; ++j) sum += f[j].first;
        if (2 * sum < s) {
            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 {
            sum = 0;
            int len = 0;
            for (int j = 0; j < k; ++j) {
                sum += f[j].first;
                len++;
                if (2 * sum >= s) break;
            }
            if (len == k) {
                for (auto [val, idx] : f) ans.push_back(idx);
                return ans;
            }
        }
        //cout << d << ' '<< k << endl;
    }
    return ans;
}