#pragma GCC optimize("O3,unroll-loops")
#include<iostream>
#include<vector>
using namespace std;

int ord[2000005], val[2000005];
bool ispl[2000005];

const int B = 3;
const int PASI = 19;

int idk[B][2000005], pozidk[B];

std::vector<int> solve(std::vector<int> A)
{
    for(int i=0;i<A.size();i++)
    {
        ord[i] = i;
        val[i] = A[i];
    }


    int r;
    for(int pas=0;pas<PASI;pas++)
    {
        for(int c=0;c<B;c++)
            pozidk[c] = 0;
        for(int i=0;i<A.size();i++)
        {
            r = val[ord[i]] % B;
            idk[r][pozidk[r]++] = ord[i];
        }

        int poz = 0;
        for(int c=0;c<B;c++)
            for(int i=0;i<pozidk[c];i++)
                ord[poz++] = idk[c][i];

        for(int i=0;i<A.size();i++)
            val[i] /= B;
    }





    long long dif = 0;
    int i;
    for(int u=0;u<A.size();u++)
    {
        i = ord[u];
        if(dif < 0)
        {
            dif += A[i];
            ispl[i] = 1;
        }
        else
        {
            dif -= A[i];
            ispl[i] = 0;
        }
    }


    vector<int> sol(A.size());
    int unde = 0;
    if(dif > 0)
    {
        for(int u=0;u<A.size();u++)
        {
            i = ord[u];
            if (ispl[i])
                sol[unde++] = i;
        }

        for(int u=0;u<A.size();u++)
        {
            i = ord[u];
            if (!ispl[i])
                sol[unde++] = i;
        }
    }
    else
    {
        for(int u=0;u<A.size();u++)
        {
            i = ord[u];
            if (!ispl[i])
                sol[unde++] = i;
        }

        for(int u=0;u<A.size();u++)
        {
            i = ord[u];
            if (ispl[i])
                sol[unde++] = i;
        }
    }
    return sol;
}