#include "partition.h"
#include <vector>

typedef long long llong;

const int MAXN = 1e6 + 10;
const int MAXLOG = 26;

int n;
int a[MAXN];
std::vector < int > to[MAXLOG];
int cnt[MAXLOG];
int lg[MAXN];
llong sum;

int getdiff(std::vector < int >& p)
{
    llong cur = 0;

    for(int i = 0; i < p.size(); i++)
    {
        cur += a[p[i]];

        if(2LL * cur >= sum)
            return abs((i + 1) - (n - i - 1));
    }

    return -1;
}

std::vector < int > solve(std::vector < int > A) 
{
    n = A.size();

    sum = 0;

    for(int i = 0; i < n; i++)
    {
        a[i] = A[i];
        sum += a[i];
    }

    for(int i = 0; i < MAXLOG; i++)
    {
        to[i].clear();
        cnt[i] = 0;
    }

    for(int i = 0; i < n; i++)
    {
        lg[i] = 0;

        while(A[i] != 1)
        {
            lg[i]++;
            A[i] /= 2;
        }

        to[lg[i]].push_back(i);
    }

    std::vector < int > ost;

    std::vector < int > s1;
    std::vector < int > s2;

    for(int i = 0; i < MAXLOG; i++)
    {
        if(to[i].empty())
            continue;

        cnt[i] += (to[i].size() / 2);    

        if(to[i].size() % 2)
        {
            ost.push_back(to[i].back());
        }
    }

    if(!ost.empty())
    {
        int sz = ost.size() / 2 + ost.size() % 2;

        for(int i = 0; i < sz - 1; i++)
        {
            cnt[lg[ost[i]]]++;
        }

        cnt[lg[ost.back()]]++;
    }

    std::vector < int > ans;

    for(int i = 0; i < MAXLOG; i++)
    {
        if(to[i].empty())
            continue;

        while(cnt[i]--)
        {
            s1.push_back(to[i].back());
            to[i].pop_back();
        }

        while(!to[i].empty())
        {
            s2.push_back(to[i].back());
            to[i].pop_back();
        }
    }

    for(int idx : s1)
    {
        ans.push_back(idx);
    }
    
    for(int idx : s2)
    {
        ans.push_back(idx);
    }

    //cout << "Diff : " << getdiff(ans) << endl;

    return ans;
}
