#include "partition.h"
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<utility>
#include<queue>
#include<map>
//#define int long long
#define ff first
#define ss second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end();
#define pii pair<int,int>
using namespace std;
const int N = 5 * 1e7 + 5;
int n,m,k,l;
int fix[N],vis[N];
vector <int> g[N];
vector <int> ans,a1,a2;
std::vector<int> solve(std::vector<int> A) {
    n = A.size();
    int mx = -1;
    int sum = (1 + n) / 2 * n;
    if(n % 4 == 0){
        for (int i = 0; i < n / 2; i++) {
            if (i % 2 == 0) {
                ans.pb(i);
                ans.pb(n - 1 - i);
                vis[i] = 1;
                vis[n - 1 - i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if(vis[i] == 1) continue;
            ans.pb(i);
        }
    }
    if (n % 2 == 0 and n % 4 == 2) {
        for (int i = 0; i < (n - 1) / 2; i++) {
            if (i % 2 == 0) {
                ans.pb(i);
                ans.pb(n - 1 - i);
                vis[i] = 1;
                vis[n - 1 - i] = 1;
            }
        }
        ans.pb(n / 2); vis[n / 2] = 1;
        ans.pb((n / 2) - 1); vis[(n / 2) - 1];
        for (int i = 0; i < n; i++) {
            if(vis[i] == 1) continue;
            ans.pb(i);
        }
    }
    if (n % 2 == 1) {
        for (int i = 0; i < n / 2; i++) {
            if (i % 2 == 0) {
                ans.pb(i);
                ans.pb(n - 1 - i);
                vis[i] = 1;
                vis[n - 1 - i] = 1;
            }
        }
        ans.pb(n / 2); vis[n / 2] = 1;
        for (int i = 0; i < n; i++) {
            if(vis[i] == 1) continue;
            ans.pb(i);
        }
    }
    return {ans};
}
