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

#define ll long long
#define pb push_back
#define ff first
#define sc second
#define pii pair<int, int>

const int maxN = 1e6 + 25;
const int inf = 1e9;
const ll big_inf = 1e18;
const int mod = 1e9 + 7;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    vector<pii> vec(n);
    for(int i = 0; i < n; i++) {
        vec[i].ff = A[i];
        vec[i].sc = i;
    }
    sort(vec.begin(), vec.end());
    vector<int> a(n);
    int l = 0, r = n - 1;
    bool cur = 0;
    for(int i = 0; i < n; i++) {
        if(cur) {
            a[l] = vec[i].sc;
            l++;
            cur = 1 - cur;
        }
        else {
            a[r] = vec[i].sc;
            r--;
            cur = 1 - cur;
        }
    }
    return a;
}


// extern vector<int> solve(vector<int> A);
// int main () {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     int t;
//     cin >> t ;
//     for (int test=1; test<=t; test++) {
//         int n;
//         cin >> n ;
//         vector <int> a(n);
//         for (int i=0; i<n; i++) {
//             cin >> a[i] ;
//         }

//         for (auto ind : solve(a)) {
//             cout << ind << " ";
//         }
//         cout << endl ;
//     }
//     cout << endl ;
//     return 0;
// }
