#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> solve(std::vector<int> A) {
    int n=A.size();
    vector<int> a=A;
    for(int i=0;i<n;i++)a[i]=__countr_zero(a[i]);
    vector<int> ans(n);
    vector<int> mp(26);
    int j=0;
    int o=n-1;
    for(int i=0;i<n;i++){
        mp[a[i]]++;
    }
    vector<int> m2(26);
    vector<int> v;
    int ma=-1;
    int mid=-1;
    for(int i=0;i<n;i++){
        if(mp[a[i]]>=2){
            m2[a[i]]++;
            if(m2[a[i]]&1==1 and m2[a[i]]!=mp[a[i]]){
                ans[j]=i;
                j++;
            }
            else if(m2[a[i]]&1==0){
                ans[o]=i;
                o--;
            }
            else{
                v.push_back(i);
                if(ma<a[i]){
                    ma=a[i];
                    mid=i;
                }
            }
        }
        else{
            if(ma<a[i]){
                ma=a[i];
                mid=i;
            }
            v.push_back(i);
        }
    }
    int k=0;
    if(j<=o){
        ans[((n+1)/2)-1]=mid;
    }
    for(int i=j;i<=o;i++){
        if(v[i-j-k]==mid){
            k--;
        }
        if(i+1==(n+1)/2){
            k++;
            continue;
        }
        else if(i+1<(n+1)/2){
            ans[i]=v[i-j-k];
        }
        else{
            ans[i]=v[i-j-k];
        }
    }
    if(n==1)ans[0]=0;
    return ans;
}