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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

// const int K = 1 << 15;
// int cnt[K];

// void reset() {
//     for (int i = 0; i < K; ++i) cnt[i] = 0;
// }

// vi bucket_sort(vi &A) {
//     int n = A.size();
//     vi ans(n);

//     reset();
//     for (int x : A) cnt[x | (K - 1)]++;
//     for (int i = 1; i < K; ++i) cnt[i] += cnt[i - 1];
    
//     reset();
//     for (int x : A) cnt[x >> 15]++;
//     for (int i = 1; i < K; ++i) cnt[i] += cnt[i - 1];

// }

vi solve(vi A) {
    int n = A.size();
    vi p(n);
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sort(p.begin(), p.end(), [&, A] (int i, int j) {
        return A[i] < A[j];
    });
    // if (n < 1e5) {

    // } else p = bucket_sort(A);
    if (n % 2 == 1) {
        vi ans(n);
        for (int i = 0; i < n; i += 2)
            ans[i / 2] = p[i];
        for (int i = 1; i < n; i += 2)
            ans[(n + i) / 2] = p[i];
        return ans;
    } else {
        vi ans(n);
        for (int i = 1; i < n; i += 2)
            ans[i / 2] = p[i];
        for (int i = 0; i < n; i += 2)
            ans[(i + n) / 2] = p[i];
        return ans;
    }
}