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

std::vector<int> solve(std::vector<int> A) {
    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};
    }
    sort(v.begin(), v.end(), std::greater<std::pair<long long, int>>());
    std::stack<int> l;
    std::queue<int> r;
    for (int i = 0; i < n; ++i) {
        if (i % 2) {
            r.push(v[i].second);
        } else {
            l.push(v[i].second);
        }
    }
    std::vector<int> ans;
    while (!l.empty()) {
        ans.push_back(l.top());
        l.pop();
    }
    while (!r.empty()) {
        ans.push_back(r.front());
        r.pop();
    }
    return ans;
}
