#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
extern vector<int> solve(vector<int> A);
std::vector<int> solve(std::vector<int> A)
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    vector<pair<int,int>>vec;int n=(int)A.size();
    bool subtask4=true;
    for (int i=0;i<n;i++)
    {
        if (A[i]!=i+1) {subtask4=false;break;}
    }
    if (subtask4)
    {
        vector<int> answer;
        int pointerl=1,pointerr=n;
        while (pointerl<pointerr) {answer.push_back(pointerl-1);answer.push_back(pointerr-1);pointerl++;pointerr--;}
        if (pointerl==pointerr) answer.push_back(pointerl-1);
        if (n%4==2) swap(answer[n/2-1],answer[n-1]);
        return answer;
    }
    for (int i=0;i<n;i++) vec.push_back({A[i],i});
    sort(vec.begin(),vec.end());bool subtask1=true;
    for (int i=0;i<n;i+=2)
    {
        if (vec[i].first!=vec[i+1].first) {subtask1=false;break;}
    }
    if (subtask1 and n%2==0)
    {
        vector<int> answer;
        for (int i=0;i<n;i+=2) answer.push_back(vec[i].second);
        for (int i=1;i<n;i+=2) answer.push_back(vec[i].second);
        return answer;
    }
    bool subtask2=true;
    for (int i=0;i<n;i++)
    {
        ///iz nepoznatog razloga ne radi
        if (i==25) {subtask2=false;break;}
        if (A[i]!=(1<<i)) {subtask2=false;break;}
    }
    if (subtask2)
    {
        vector<int> answer;
        for (int i=1;i<(n+1)/2;i++) answer.push_back(i-1);
        answer.push_back(n-1);
        for (int i=(n+1)/2;i<n;i++) answer.push_back(i-1);
        return answer;
    }
    if (n<=7)
    {
        long long suma=0;for (int i=0;i<n;i++) suma+=(long long)A[i];
        vector<int> position;for (int i=0;i<n;i++) position.push_back(i);
        long long currsum=0;int number=0,minrazlika=n;
        for (int pos:position)
        {
            currsum+=(long long)A[pos];number++;
            if (currsum>=suma/2) break;
        }
        minrazlika=min(minrazlika,abs(number-(n-number)));vector<int> answer=position;
        while (next_permutation(position.begin(),position.end()))
        {
            currsum=(long long)0;number=0;
            for (int pos:position)
            {
                currsum+=(long long)A[pos];number++;
                if (currsum>=suma/2) break;
            }
            if (abs(number-(n-number))<minrazlika) {minrazlika=abs(number-(n-number));answer=position;}
        }
        return answer;
    }
}