#include<bits/stdc++.h>
using namespace std;
std::vector<int32_t> solve(std::vector<int32_t> A)
{
    vector<pair<int,int>> mici, mari;
    for(int i=0;i<A.size();i++)
    {
        if(A[i] <= 1e6)
        {
            mici.push_back({A[i], i});
        }
        else
        {
            mari.push_back({A[i], i});
        }
    }
    
    sort(mici.begin(), mici.end());

    vector<pair<int,int>> v;
    for(auto x:mici)
        v.push_back(x);
    for(auto x:mari)
        v.push_back(x);


    long long dif = 0;
    vector<pair<int,int>> pl,mi;
    for(int i=0;i<v.size();i++)
    {
        if(dif < 0)
        {
            dif += v[i].first;
            pl.push_back(v[i]);
        }
        else
        {
            dif -= v[i].first;
            mi.push_back(v[i]);
        }
    }


    vector<int32_t> sol;
    if(dif > 0)
    {
        for(auto [_,x]:pl)
            sol.push_back(x);
        for(auto [_,x]:mi)
            sol.push_back(x);
    }
    else
    {
        for(auto [_,x]:mi)
            sol.push_back(x);
        for(auto [_,x]:pl)
            sol.push_back(x);
    }
    return sol;
}
