#include <bits/stdc++.h>
#include "partition.h"

using namespace std;

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

    unordered_map<int,int>lg;
    int currlg=0;
    for(int i=1;i<=(1<<25);i*=2)
    {
        lg[i]=currlg;
        currlg++;
    }

    vector<vector<int>>v(26);

    for(int i=0;i<n;i++)
    {
        v[lg[A[i]]].push_back(i);
    }

    /*for(int i=0;i<=25;i++)
    {
        cout<<i<<endl;
        for(int j : v[i])
            cout<<j<<' ';
        cout<<endl;
    }*/

    vector<int>l,r,p;

    if(n%2==1)
    {
        int idx=0;
        for(int i=0;i<=25;i++)
        {
            for(int j : v[i])
            {
                if(idx%2==0)
                    l.push_back(j);
                else
                    r.push_back(j);
                idx++;
            }
        }
        for(int i : l)
            p.push_back(i);
        for(int i : r)
            p.push_back(i);
    }
    else
    {
        int idx=0;
        for(int i=0;i<=25;i++)
        {
            for(int j : v[i])
            {
                if(idx%2==1)
                    l.push_back(j);
                else
                    r.push_back(j);
                idx++;
            }
        }
        for(int i : l)
            p.push_back(i);
        for(int i : r)
            p.push_back(i);
    }

    return p;
}
