#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> solve(std::vector<int> A) {
    vector<int> ans;
    int n=A.size();
    pair<int,int> a[n];
    for(int i=0;i<n;i++){
        a[i].first=A[i];
        a[i].second=i;
    }
    sort(a,a+n);
    bool w=true,x=true,y=true;
    for(int i=0;i<n;i+=2){
        if(a[i].first!=a[i+1].first) w=false;
    }
    for(int i=0;i<n;i++){
        if(a[i].first!=(1<<i)) x=false;
        if(a[i].first!=i+1) y=false;
    }
    if(w){
        for(int i=0;i<n;i+=2){
            ans.push_back(a[i].second);
        }
    }
    else if(x){
        ans.push_back(n-1);
    }
    else if(y){
        int r=n%4;
        for(int i=r;i<(n-r)/2+r;i++){
            ans.push_back(i);
            ans.push_back(n-i-1);
        }
        if(r==1){
            ans.push_back(0);
        }
        if(r==2){
            ans.push_back(1);
        }
        if(r==3){
            ans.push_back(0);
            ans.push_back(1);
        }
    }
    return ans;
}
