#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> solve(std::vector<int> A)
{
    int n=A.size();
    vector<pair<int, int>>A2;
    map<int, int>freq;
    bool paren=true;
    bool posl=true;
    for(int i=0;i<n;i++)
    {
        A2.push_back({A[i], i});
        freq[A[i]]++;
        if(A[i]!=i+1)
        {
            posl=false;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(freq[A[i]]%2!=0)
        {
            paren=false;
        }
    }
    sort(A2.begin(), A2.end());
    vector<int>V;
    if(posl)
    {
        if(n%2==1)
        {
            int x=n/2;
            int y=n/2+1;
            if(y%2==0)
            {
                for(int i=1;i<=y/2;i++)
                {
                    V.push_back(i-1);
                }
                for(int i=n;i>n-y/2;i--)
                {
                    V.push_back(i-1);
                }
                for(int i=y/2+1;i<=n-y/2;i++)
                {
                    V.push_back(i-1);
                }
            }
            else
            {
                for(int i=1;i<=y/2+1;i++)
                {
                    V.push_back(i-1);
                }
                for(int i=n;i>n-y/2;i--)
                {
                    V.push_back(i-1);
                }
                for(int i=y/2+2;i<=n-y/2;i++)
                {
                    V.push_back(i-1);
                }
            }
        }
        else{
            int x=n/2;
            if(x%2==0)
            {
                for(int i=1;i<=x/2;i++)
                {
                    V.push_back(i-1);
                }
                for(int i=n;i>n-x/2;i--)
                {
                    V.push_back(i-1);
                }
                for(int i=x/2+1;i<=n-x/2;i++)
                {
                    V.push_back(i-1);
                }
            }
            else
            {
                int y=x/2+1;
                for(int i=2;i-1<=y;i++)
                {
                    V.push_back(i-1);
                }
                for(int i=n;i>n-(y-1);i--)
                {
                    V.push_back(i-1);
                }
                V.push_back(0);
                for(int i=y+2;i<=n-(y-1);i++)
                {
                    V.push_back(i-1);
                }
            }
        }
        return {V};
    }
    if(paren)
    {
        for(int i=0;i<n;i++)
        {
            int x=freq[A2[i].first];
            freq[A2[i].first]=0;
            for(int j=i;j<i+x/2;j++)
            {
                V.push_back(A2[j].second);
                A2[j].first=-1;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(A2[i].first!=-1)
            {
                V.push_back(A2[i].second);
            }
        }
        return {V};
    }
    else
    {
        if(n%2==1)
        {
            for(int i=0;i<(n-2)/2;i++)
            {
                V.push_back(A2[i].second);
                A2[i].first=-1;
            }
            V.push_back(A2[n-1].second);
            for(int i=0;i<n-1;i++)
            {
                if(A2[i].first!=-1)
                {
                    V.push_back(A2[i].second);
                }
            }
        }
        else{
            for(int i=0;i<(n-1)/2;i++)
            {
                V.push_back(A2[i].second);
                A2[i].first=-1;
            }
            V.push_back(A2[n-1].second);
            for(int i=0;i<n-1;i++)
            {
                if(A2[i].first!=-1)
                {
                    V.push_back(A2[i].second);
                }
            }
        }
        return {V};
    }
}
