#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();
    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;
    }
    if (n<=7)
    {
        int suma=0;for (int i=0;i<n;i++) suma+=A[i];
        vector<int> positions;for (int i=0;i<n;i++) positions.push_back(i);
        int currsum=0,number=0,minrazlika=n;
        for (int pos:positions)
        {
            currsum+=A[pos];number++;if (currsum>=suma/2) {minrazlika=min(minrazlika,abs(number-(n-number)));break;}
        }
        vector<int> answer=positions;
        while (next_permutation(positions.begin(),positions.end()))
        {
            currsum=0;number=0;
            for (int pos:positions)
            {
                currsum+=A[pos];number++;
                if (currsum>=suma/2)
                {
                    minrazlika=min(minrazlika,abs(number-(n-number)));
                    if (minrazlika==abs(number-(n-number))) answer=positions;
                    break;
                }
            }
        }
        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=n-1;i>=0;i--) answer.push_back(i);
        return answer;
    }
    bool subtask4=true;
    for (int i=0;i<n;i++)
    {
        if (A[i]!=i+1) {subtask4=false;break;}
    }
    if (subtask4)
    {
        ///iz nekog razloga TLE?
        vector<int> answer;
        if (n%4==0)
        {
            int pointerl=1,pointerr=n;
            while (pointerl<pointerr)
            {
                answer.push_back(pointerl-1);pointerl++;
                answer.push_back(pointerr-1);pointerr--;
            }
            return answer;
        }
        else if (n%4==1)
        {
            int pointerl=2,pointerr=n;int targetparova=(n-1)/4;int curr=0;
            while (curr!=targetparova)
            {
                answer.push_back(pointerl-1);pointerl++;
                answer.push_back(pointerr-1);pointerr--;
                curr++;
            }
            answer.push_back(0);
            while (pointerl<pointerr)
            {
                answer.push_back(pointerl-1);pointerl++;
                answer.push_back(pointerr-1);pointerr--;
            }
            return answer;
        }
        else if (n%4==2)
        {
            int pointerl=1,pointerr=n;int targetparova=n/4;int curr=0;
            while (curr!=targetparova)
            {
                answer.push_back(pointerl-1);pointerl++;
                answer.push_back(pointerr-1);pointerr--;
                curr++;
            }
            answer.push_back(n/2);
            while (pointerr!=n/2+1)
            {
                answer.push_back(pointerl-1);pointerl++;
                answer.push_back(pointerr-1);pointerr--;
            }
            answer.push_back(n/2-1);return answer;
        }
        else if (n%4==3)
        {
            int pointerl=2,pointerr=n;int targetparova=(n-1)/4;int curr=0;
            while (curr!=targetparova)
            {
                answer.push_back(pointerl-1);pointerl++;
                answer.push_back(pointerr-1);pointerr--;
                curr++;
            }
            answer.push_back(n/2);answer.push_back(0);
            while (pointerl!=n/2+1)
            {
                answer.push_back(pointerl-1);pointerl++;
                answer.push_back(pointerr-1);pointerr--;
            }
            answer.push_back(n/2+1);return answer;
        }
    }
}