#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
vector<int> a;
vector<int> ind;
vector<bool> used;
// vector<int> mine;

std::vector<int> solve(std::vector<int> A)
{
    // mine.clear();
    a = A;
    n = a.size();
    ind.resize(n, 0);
    used.resize(n, false);
    used.assign(n, false);
    ll tt = 0;
    for(int i = 0; i < n;i ++)
    {
        tt += a[i];
        ind[i] = i;
    }
    sort(ind.begin(), ind.end(), [&](int x, int y) {
        return a[ind[x]] < a[ind[y]];
    });
    int len = (n + 1) / 2;
    int sum = 0;
    set<int> st;
    for(int i = 0; i < len; i++)
    {
        sum += a[ind[i]];
        st.insert(i);
    }
    for(int i = len; i < n; i++) // vreau sa il bag pe asta dar vreau si sa scot cel mai mic a.i. sa nu ma supar
    {
        int maxim = a[ind[*st.rbegin()]];
        int new_maxim = a[ind[i]];
        int best = -1;
        for(int x : st)
        {
            if(sum - a[ind[x]] - new_maxim < (tt + 1) / 2)
                best = x;
        }
        assert(best != -1);
        st.erase(best);
        sum -= a[ind[best]];
        st.insert(i);
        sum += a[ind[i]];
    }
    // for(int i = 0; i < n; i++)
    //     cerr << ind[i] << ' ';
    vector<int> ans;
    for(int x : st)
    {
        used[ind[x]] = true;
        ans.push_back(ind[x]);
    }
    for(int i = 0; i < n; i++)
    {
        // cerr << used[i] << ' ';
        if(!used[ind[i]])
            ans.push_back(ind[i]);
    }
    // cerr << '\n';
    // cerr << "D" << ans.size() << '\n';
    return ans;
    // ll sum = 0, maxim = a[ind[n - 1]];
    // int p = n - 1;
    // while(p >= 0 && sum + a[ind[p]] - maxim < (tt + 1) / 2)
    // {
    //     taken.push_back(p);
    //     sum += a[ind[p]];
    //     p -= 2;
    // }
    // p++;
    // p = max(p, 0);
    // vector<int> wh;

}