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

using namespace std;

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

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

    map<int, vector<int> > vf;
    for(int i = 0; i < n; i++) vf[ a[i] ].push_back(i);

    bool par = 1;
    for(const auto &x : vf){
        if(x.second.size() % 2) par = 0;
    }

    if(par){
        vector<int> sol;
        sol.resize(n);

        int i1 = 0, i2 = n - 1;
        for(const auto &x : vf){
            for(int i = 0; i < x.second.size(); i++){
                if(i < x.second.size() / 2) sol[i1++] = x.second[i];
                else sol[i2--] = x.second[i];
            }
        }

        return sol;
    }

    // daca toate is 2 ^ i
    bool subtask2 = 1;
    for(int i = 0; i < n; i++){
        if(a[i] != (1 << i)) subtask2 = 0;
    }

    if(subtask2){
        vector<int> sol;
        for(int i = 0; i < n - 1; i++) sol.push_back(i);
        sol.insert(sol.begin() + n / 2 - 1, n - 1);
        return sol;
    }
}
