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

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    vector<int> ans;
#define int long long
    int sum = n * (n + 1) / 2;
    set<int> free;
    set<int> used;
    for (int i = 1; i <= n; i++) {
        free.insert(i);
    }
    int cur = 0;
    while (cur < (sum + 1) / 2) {
        cur += *free.rbegin();
        used.insert(*free.rbegin());
        free.erase(--free.end());
    }
    while (used.size() < n / 2) {
        int x = *used.rbegin();
        used.erase(--used.end());
        int y = *free.rbegin();
        free.erase(--free.end());
        free.insert(x);
        used.insert(y);
        auto it = free.lower_bound(x - y);
        if (it == free.end()) {
            it--;
        }
        used.insert(*it);
        free.erase(it);
    }
    ans.insert(ans.end(), used.begin(), used.end());
    ans.insert(ans.end(), free.begin(), free.end());
    #undef int
    for (int &i : ans) {
        i--;
    }
    return ans;
}