#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
const int MAXN=1e7;

int nr;

int optmask=0,ans=INT_MAX;
long long S=0;


int fr[26];
int a[MAXN+1];

vector<int> solve(vector<int> A) {
    int n=A.size();
    for(int i=0; i<=25; i++) {
        fr[i]=0;
    }
    vector<int>pos[26];
    for(int i=0; i<n; i++) {
        int e=0,ac=A[i];
        a[i]=A[i];
        while(ac%2==0) {
            e++;
            ac/=2;
        }
        fr[e]++;
        pos[e].push_back(i);
    }
    vector<int>lhs,rhs;
    vector<pair<int,int>>rem;
    for(int e=0; e<=25; e++) {
        int sz=pos[e].size();
        sz/=2;
        for(int i=0; i<sz; i++) {
            lhs.push_back(pos[e][i]);
        }
        for(int i=sz; i<2*sz; i++) {
            rhs.push_back(pos[e][i]);
        }
        if(sz*2!=pos[e].size()) {
            rem.push_back({pos[e][pos[e].size()-1],e});
        }
    }
    if(rem.size()%2) {
        for(int i=0; i<rem.size(); i+=2) {
            lhs.push_back(rem[i].first);
        }
        for(int i=1; i<rem.size(); i+=2) {
            rhs.push_back(rem[i].first);
        }
    } else {
        for(int i=1; i<rem.size(); i+=2) {
            lhs.push_back(rem[i].first);
        }
        for(int i=0; i<rem.size(); i+=2) {
            rhs.push_back(rem[i].first);
        }
    }
    sort(lhs.begin(),lhs.end(),[](int x,int y) {
        return a[x]<a[y];
    });
    vector<int>res=lhs;
    for(auto it:rhs) {
        res.push_back(it);
    }
    return res;
}
/*
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t ;
    for (int test=1; test<=t; test++) {
        int n;
        cin >> n ;
        vector <int> a(n);
        for (int i=0; i<n; i++) {
            cin >> a[i] ;
        }

        for (auto ind : solve(a)) {
            cout << ind << " ";
        }
        cout << endl ;
    }
    cout << endl ;
    return 0;
}

*/
