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

using namespace std;

vector<int> solve(vector<int> a) {
    int n = a.size();
    if(n == 1) {
        return {0};
    }

    vector<int> freq[30];
    for(int i = 0; i < n; i++) {
        freq[__builtin_ctz(a[i])].push_back(i);
    }
    vector<int> pref, suff, mid;
    pref.reserve(n);
    suff.reserve(n);
    mid.reserve(n);
    int cnt = 0;
    for(int i = 0; i < 30; i++) {
        while(freq[i].size() >= 2) {
            pref.push_back(freq[i].back());
            freq[i].pop_back();
            suff.push_back(freq[i].back());
            freq[i].pop_back();
        }
        cnt += freq[i].size();
    }

    cnt = (cnt - 1) / 2;
    for(int i = 0; i < 30; i++) {
        if(!freq[i].empty() && cnt > 0) {
            mid.push_back(freq[i].back());
            freq[i].pop_back();
            cnt--;
        }
    }
    for(int i = 29; i >= 0; i--) {
        if(!freq[i].empty()) {
            mid.push_back(freq[i].back());
            freq[i].pop_back();
        }
    }

    vector<int> answer;
    for(auto it : pref) {
        answer.push_back(it);
    }
    for(auto it : mid) {
        answer.push_back(it);
    }
    for(auto it : suff) {
        answer.push_back(it);
    }
    return answer;
}
