#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "partition.h"
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const ll inf = 2e9;
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
template <class t> using oset = tree<t, null_type, less <t>, rb_tree_tag, tree_order_statistics_node_update>;
vector <int> solve(vector <int> A){
    vector <pll> v;
    int n = A.size();
    for (int i = 0 ; i < n ; i++){
        v[i] = make_pair(A[i], i);
    }
    sort(all(v));
    deque <pll> ans;
    ll reals = (accumulate(all(A), 0LL) + 1LL) / 2LL;
    ll sum = 0;
    for (int i = 0 ; i < n ; i++){
        sum += v[i].first;
        if (sum >= reals) {
            sum -= v[i].first;
            break;
        }
        ans.push_back(v[i]);
    }
    ll sz = A.size() / 2;
    if (ans.size() < sz){
        ans.push_back(v[ans.size()]);
    }
    else {
        ll ptr = ans.size();
        while (ans.size() != sz and ans.size() != (A.size() + 1) / 2){
            while (sum >= reals and ans.size() != sz and ans.size() != (A.size() + 1) / 2){
                sum -= ans.front().first;
                ans.pop_front();
            }
            if ((ans.size() == sz or ans.size() == (A.size() + 1) / 2) and sum >= reals){
                break;
            }
            sum += v[ptr].first;
            ans.push_back(v[ptr]);
            ptr++;
        }
    }
    vector <int> realans, vis(n);
    for (auto &[a, b] : ans) {
        realans.push_back(b);
        vis[b] = true;
    }
    for (int i = 0 ; i < n ; i++){
        if (!vis[i]) realans.push_back(i);
    }
    return realans;
}