#include <bits/stdc++.h>
#include "partition.h"
#define endl '\n'

using namespace std;

const int MAXN = 1e6;

int n;
vector<int>otg;
pair<int,int>a[MAXN + 5];
unordered_map<int,int>used;
vector<int>ve[30];


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

    int st = 1, cnt = 0;

    used[0] = 1;
    while(cnt <= 25)
    {
        st *= 2; cnt++;
        used[st] = cnt;
    }
    vector<int>v;

    for(int i = 0; i < A.size(); i++)
    {
        a[i] = {A[i], i};
        ve[used[A[i]]].push_back(i);
    }

    for(int i = 0; i <= 25; i++)
    {
        for(auto j: ve[i])
        {
            v.push_back(j);
        }
    }

    int mid = 0;
    if(n % 2 == 0)mid = n / 2 - 1;
    else mid = n / 2;

    for(int i = 0; i < mid; i++)
    {
        otg.push_back(v[i]);
    }
    otg.push_back(v[n - 1]);

    for(int i = mid; i < n - 1; i++)
    {
        otg.push_back(v[i]);
    }

    return otg;
}
