# include "partition.h"
# include <bits/stdc++.h>
# define ll long long
using namespace std;

const int MAXN = 2 * 1e6 + 1123;
bool visited[MAXN];

vector<int> solve(vector<int> a)
{
    int n = (int)a.size();
    if(n == 1) return {0};
    vector<pair<int, int>> order;
    vector<int> answer;
    vector<int> marked(n + 1, 0);
    int marker = 0;
    ll s = 0;
    for(int i = 0; i < n; i++)
    {
        visited[i] = false;
        order.push_back({a[i], i});
        s += a[i];
    }

    sort(order.begin(), order.end());

    for(int wanted_size = n / 2; wanted_size <= n; wanted_size++)
    {
        deque<int> dq;
        ll current = 0;

        for(int i = 0; i < wanted_size; i++)
        {
            current += order[i].first;
            dq.push_back(i);
            marked[i] = marker;
        }

        marker++;
        bool flag = false;
        int r = n - 1;
        bool change;

        while(2 * current < s)
        {
            int small = dq.front();
            int big = dq.back();
            dq.pop_front();
            change = false;

            for(int i = r; i >= 0; i--)
            {
                if(marked[i] != marker)
                {
                    marked[i] = marker;
                    dq.push_back(i);
                    current += (a[order[i].second] - a[order[small].second]);
                    marked[small] = marker - 1;
                    r = i - 1;
                    change = true;
                    break;
                }
            }

            if(2 * current >= s)
            {
                flag = true;
                break;
            }

            if(!change) break;
        }

        if(flag)
        {
            for(auto& i : dq)
            {
                visited[order[i].second] = true;
                answer.push_back(order[i].second);
            }

            break;
        }

    }

    for(int i = 0; i < n; i++) if(!visited[i]) answer.push_back(i);
    return answer;
}
