#include <bits/stdc++.h>
#include "partition.h"
#define ll long long
using namespace std;

bool viz[10000005];

vector<int> solve(vector<int> v){
    int n = v.size();
    for(int i = 0; i <= n; i++) viz[i] = 0;
    vector<int> ans;
    int l = 1, r = n - 2;
    while(l < r){
        ans.push_back(l);
        ans.push_back(r);
        viz[l] = viz[r] = 1;
        l += 2;
        r -= 2;
    }
    l--;
    r++;
    if(r - l + 1 == 1){
        ans.push_back(l);
        viz[l] = 1;
    }
    else if(r - l + 1 == 2){
        ans.push_back(r);
        viz[r] = 1;
    }
    else if(r - l + 1 == 3){
        viz[l] = viz[r] = 1;
        ans.push_back(l);
        ans.push_back(r);
    }
    for(int i = 0; i < n; i++){
        if(!viz[i]) ans.push_back(i);
    }
    return ans;
}
