#define ll long long
#define se second
#define fi first
using namespace std;
#include<utility>
#include<algorithm>
#include<vector>

const char nl = '\n';

    vector <int> solve(vector <int> a) {
        int n = a.size();
        ll s = 0;
        vector <pair <int, int> > p;
        for (int i = 0; i < n; i++) {
            p.push_back({a[i], i});
            s += a[i];
        }
        ll need = s / 2 + s % 2;
        sort(p.begin(), p.end());
        vector <int> ans;
        vector <int> us(n);
        vector <ll> pref(n + 1);
        for (int i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] + p[i - 1].fi;
        }
        int cnt = 0;
        ll cur = 0;
        int len = n / 2 + n % 2;
        /*cout << len << ' ' << need << nl;
        for (auto it : pref) {
            cout << it << ' ';
        }
        cout << nl;*/
        for (int i = n - 1; i >= 0; i--) {
            if (cnt == len) {
                break;
            }
            if (i + 1 == len - cnt) {
                ans.push_back(p[i].se);
                cnt++;
                cur += p[i].fi;
            } else if (pref[i] - pref[i - (len - cnt)] + cur >= need) {
                continue;
            } else {
                ans.push_back(p[i].se);
                cnt++;
                cur += p[i].fi;
            }
        }
        for (auto it : ans) {
            us[it] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (!us[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }