#include <bits/stdc++.h>
#include "partition.h"

std::vector<int> solve(std::vector<int> A) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = A.size();
    std::vector<std::pair<long long, int>> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = {A[i], i};
    }
    int half = ceil(n / 2.0);
    sort(v.begin(), v.end(), std::greater<std::pair<long long, int>>());
    std::vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        if (i % 2) {
            ans[half + i / 2] = v[i].second;
        } else {
            ans[half - 1 - i / 2] = v[i].second;
        }
    }
    return ans;
}