#include "partition.h"
#include "bits/stdc++.h"
using namespace std;

vector<int>solve(vector<int>A)
{
      int n=A.size();
      if(n%2==0){
            vector<int>v1,v2;
            int turn=1;
            for(int i=0;i<n;i+=2){
                  if((n/2)%2==0&&turn==n/2-1){
                        v1.push_back(i+1);
                        v2.push_back(i);
                        continue;
                  }
                  if((n/2)%2==1&&turn==n/2){
                        v1.push_back(i+1);
                        v2.push_back(i);
                        continue;
                  }
                  if(turn&1){
                        v1.push_back(i);
                        v2.push_back(i+1);
                  }
                  else{
                        v1.push_back(i+1);
                        v2.push_back(i);
                  }
                  turn++;
            }
            vector<int>res;
            for(int x:v1) res.push_back(x);
            for(int x:v2) res.push_back(x);
            return res;
      }
      else{
            vector<int>v1,v2,res;
            int turn=1;
            for(int i=1;i<n;i+=2){
                  if(turn&1){
                        v1.push_back(i);
                        v2.push_back(i+1);
                  }
                  else{
                        v1.push_back(i+1);
                        v2.push_back(i);
                  }
                  turn++;
            }
            v1.push_back(0);
            for(int x:v1) res.push_back(x);
            for(int x:v2) res.push_back(x);
            return res;
      }
}
