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

using namespace  std;

const int maxn=1e5+10;
const int mod=1e9+7;


std::vector<int> solve(std::vector<int> A)
{
    int n=A.size();

    map<int,int>m;
    bool ok2=1;
    bool inc=1;
    int p[26];
    p[0]=1;
    for (int i=1;i<26;i++) {
        p[i]=p[i-1]*2;
    }
    for (int i=0;i<n;i++) {
        m[A[i]]++;
        bool t2=0;
        for (int s=0;s<26;s++) {///stepen na 2
            if (A[i]==p[s]) {
                t2=1;
                break;
            }
        }
        if (t2==0)ok2=0;
        if (A[i]!=i+1)inc=0;///dali e inc za 1
    }
    bool even=1;///dali paren broj pati se pojavuva
    for (auto ax:m) {
        if (ax.second%2!=0) {
            even=0;
            break;
        }
    }
    vector<int>ans;
    if (even) {///Sub1
        sort(A.begin(),A.end());
        for (int i=0;i<n;i+=2) {
            ans.push_back(A[i]);
        }
        for (int i=1;i<n;i+=2) {
            ans.push_back(A[i]);
        }
        return ans;
    }
    if (ok2==1) {///Sub 2 and 3
        vector<int>eks;
        vector<int>d;
        vector<int>m;
        for (int i=0;i<n;i++) {
            int j=i-1;
            while (j+1<n && A[j+1]==A[i]) {
                j++;
            }
            int cnt=j-i+1;
            if (cnt%2==1) {
                eks.push_back(A[i]);
                cnt--;
            }
            for (int idx=0;idx<cnt;idx++) {
                if (idx%2==0)
                ans.push_back(A[i]);
                if (idx%2==1)
                m.push_back(A[i]);
            }
            i=j;
        }
        sort(eks.begin(),eks.end());
        for (int idx=0;idx<eks.size()/2;idx++) {
            ans.push_back(eks[idx]);
        }
        ans.push_back(eks.back());
        for (int idx=(eks.size()/2)+1;idx<eks.size()-1;idx++) {
            ans.push_back(eks[idx]);
        }
        for (auto x:m) {
            ans.push_back(x);
        }
        return ans;
    }
    if (inc==1) {///Sub 4
        int i=0;
        int j=n-1;
        vector<int>m;
        int koj=0;
        while (i<j) {
            if (koj==0) {
                ans.push_back(A[i]);
                ans.push_back(A[j]);
            }
            else {
                m.push_back(A[i]);
                m.push_back(A[j]);
            }
            koj=(koj+1)%2;
            i++;
            j--;
        }
        if (i==j) {
            ans.push_back(A[i]);
        }
        for (auto ax:m) {
            ans.push_back(ax);
        }
        return ans;
    }
}
