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

using namespace std;
using ll = long long;

vector< pair<ll, int> > A;
ll S = 0;
int n;
vector<int> eu, sol;
int mini = 0;

vector<int> solve(vector<int> a){
    n = a.size();

    if(n == 1) return {0};

    bool subtask = 1;
    for(int i = 0; i < n; i++){
        if(a[i] != i + 1) subtask = 0;
    }

    if(subtask){
        vector<int> sol(n);
        for(int i = 0; i < n; i++) sol[i] = -1;
        int i1 = 0, i2 = n - 1;
        int st = 0, dr = n - 1;
        for(int i = 0; i < n / 2; i++){
            if(st % 2 == 0){
                sol[i1++] = dr;
                sol[i1++] = st;
            }else{
                sol[i2--] = st;
                sol[i2--] = dr;
            }
            st++; dr--;
        }

        for(int i = i1; i <= i2; i++) sol[i] = st++;
        return sol;
    }

    subtask = 1; // is toate puteri de 2?
    for(int i = 0; i < n; i++){
        if((a[i] & (a[i] - 1)) != 0) subtask = 0;
    }


    vector< pair<ll, int> > v;
    v.resize(n);
    if(subtask){
        vector<int> mp[26];
        for(int i = 0; i < n; i++){
            mp[ (int)log2(a[i]) ].push_back(i);
        }

        int it = 0;
        for(int i = 0; i <= 25; i++){
            for(int j = 0; j < mp[i].size(); j++){
                v[it++] = {(1 << i), mp[i][j]};
            }
        }
    }else{
        for(int i = 0; i < n; i++) v[i] = {a[i], i};
        sort(v.begin(), v.end());
    }
    S = 0;
    for(int i = 0; i < n; i++) S += v[i].first;

    ll sp[n + 1];
    sp[0] = 0;
    for(int i = 0; i < n; i++) sp[i + 1] = sp[i] + v[i].first;

    int len = n / 2 - 1;
    ll suma = 0, cnt = 0;
    vector<int> poz;
    vector<int> alt;
    for(int i = n - 2; i >= 0; i--){
        if(cnt == len){
            alt.push_back(v[i].second);
            continue;
        }
        suma += v[i].first;
        cnt++;
        //cout << "i = " << i << " suma = " << suma << "\n";
        if(suma * 2LL >= S){ suma -= v[i].first; cnt--; alt.push_back(v[i].second); }
        else if((suma + sp[len - cnt]) * 2LL >= S){ suma -= v[i].first; cnt--; alt.push_back(v[i].second); }
        else poz.push_back(v[i].second);
    }

    poz.push_back(v[n - 1].second);
    for(int i = 0; i < alt.size(); i++) poz.push_back(alt[i]);

    return poz;
}