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

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    vector<int> ans;

    set<int> st;
    for (int i=0; i<n; i++)
        st.insert(i);

    int t = 0;
    while (2 * st.size() >= n) {
        if (!t) {
            ans.push_back(*st.begin());
            st.erase(ans.back());
        } else {
            ans.push_back(*st.rbegin());
            st.erase(ans.back());
        }
        t ^= 1;
    }

    sort(ans.begin(), ans.end());

    for (auto x : st) ans.push_back(x);

    return ans;
}
