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

using namespace std;

const int maxn = 1e5 + 5;
const int MAXPWR = 30;

int n;
int cnt[MAXPWR];
vector<int> position[MAXPWR];
vector<int> ans, other;

int findLog2(int x)
{
    int cnt = 0;

    while (x != 1)
    {
        ++cnt;
        x /= 2;
    }

    return cnt;
}

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

    for (int i = 0; i < n; ++i)
    {
        ans[i] = 0;
        int p = findLog2(A[i]);

        ++cnt[p];
        position[p].push_back(i);
    }

    int l = 0, r = n - 1;

    for (int i = 0; i < MAXPWR; ++i)
    {
        if (cnt[i] == 0) continue;

        for (int j = 0; j + 2 <= cnt[i]; j += 2)
        {
            ans[l++] = position[i][j];
            ans[r--] = position[i][j + 1];
        }

        if (cnt[i] % 2 == 1)
        {
            other.push_back(position[i].back());
        }

        position[i].clear();
    }

    int otherSz = other.size();
    swap(other[otherSz - 1], other[otherSz / 2 - 1]);

    for (int i = l; i <= r; ++i)
    {
        ans[i] = other[i - l];
    }

    return ans;
}
