#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
using ll=long long;

#pragma GCC optimize("O3")
const ll N=2e6+55;
array<ll,2>aa[N];
ll p[N],s[N],n;

vector<int>ps[33];

std::vector<int> solve(std::vector<int>a){
    n=a.size();
    for(int i=0;i<27;++i)
        ps[i].clear();
    for(int i=0;i<n;++i){
        ps[__builtin_ctz(a[i])].push_back(i);
    }
    ll lik=0;
    for(int i=0;i<27;++i){
        for(ll j:ps[i]){
            aa[lik++]={(ll)(1<<i),(ll)j};
        }
    }
    //for(int i=0;i<n;++i)
    //    aa[i]={a[i],i};
    //sort(aa,aa+n);
    fill(p,p+n+5,0ll);
    fill(s,s+n+5,0ll);
    p[0]=aa[0][0];
    for(int i=1;i<n;++i){
        p[i]=p[i-1]+aa[i][0];
    }
    s[n-1]=aa[n-1][0];
    for(int i=n-2;i>=0;--i){
        s[i]=s[i+1]+aa[i][0];
    }
    ll l=-1,r=n-1,ans=l;
    while(l<=r){
        ll md=(l+r)/2;
        ll klk=(n)/2-(md+1);
        ll sum=(md==-1?0:p[md])+s[n-klk];
        //cout<<md<<' '<<sum<<' '<<p[n-1]/2<<endl;
        if(sum*2>=p[n-1]){
            //cout<<"!"<<md<<endl;
            ans=md;
            l=md+1;
        }else
            r=md-1;
    }
    vector<int>ret;
    for(int i=0;i<=ans;++i)
        ret.push_back(aa[i][1]);
    for(int i=n-1;i>ans;--i)
        ret.push_back(aa[i][1]);
    return ret;
}
