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

using namespace std;

typedef long long llong;

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

int n;
int a[MAXN];
vector < int > to[MAXLOG];
llong sum;

bool cmp(int x, int y)
{
    return a[x] < a[y];
}

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();
    }

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

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

        to[lg].push_back(i);
    }

    vector < int > ost;

    vector < int > s1;
    vector < int > s2;

    for(int i = 0; i < MAXLOG; i++)
    {
        while(to[i].size() >= 2)
        {
            int idx1 = to[i].back();
            to[i].pop_back();
            int idx2 = to[i].back();
            to[i].pop_back();

            s1.push_back(idx1);
            s2.push_back(idx2);
        }

        if(!to[i].empty())
        {
            ost.push_back(to[i].back());
        }
    }

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

        for(int i = 0; i < sz - 1; i++)
        {
            s1.push_back(ost[i]);
        }

        s1.push_back(ost.back());

        for(int i = sz - 1; i < cnt - 1; i++)
        {
            s2.push_back(ost[i]);
        }
    }

    sort(s1.begin(), s1.end(), cmp);
    sort(s2.begin(), s2.end(), cmp);

    vector < int > ans;

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

    return ans;
}
