#include "partition.h"
#include<vector>
#include<iostream>
#include<map>
#include<set>
using namespace std;


vector<int> mn_on, cnt;
std::vector<int> solve(std::vector<int> a) {
    if (mn_on.size() != (1 << 20)) {
        mn_on.resize(1 << 20);
        cnt.resize(1 << 20);
        for (int i = 1; i < (1 << 20); i++) {
            for (int j = 0; j < 20; j++) {
                if (i & (1 << j)) {
                    mn_on[i] = j;
                    cnt[i] = cnt[i ^ (1 << j)] + 1;
                    break;
                }
            }
        }
    }
    int n = a.size();
    long long sm_all = 0;
    for (auto &i : a) {
        sm_all += i;
    }
    int ans_mask = 0;
    int mn_ans = n + 1;
    vector<int> mx(1 << n, -1);
    vector<long long> sm(1 << n, 0);
    for (int i = 1; i < (1 << n); i++) {
        mx[i] = max(mx[i ^ (1 << mn_on[i])], a[mn_on[i]]);
        sm[i] = sm[i ^ (1 << mn_on[i])] + a[mn_on[i]];
        cnt[i] = cnt[i ^ (1 << mn_on[i])] + 1;
        if (sm[i] - mx[i] >= (sm_all + 1) / 2 || sm[i] < (sm_all + 1) / 2) {
            continue;
        }
        if (mn_ans > abs(n - 2 * cnt[i])) {
            mn_ans = abs(n - 2 * cnt[i]);
            ans_mask = i;
        }
    }
    // cout << mn_ans << endl;
    vector<int> ans;
    vector<pair<int, int>> ans2;
    for (int j = 0; j < n; j++) {
        if (ans_mask & (1 << j)) {
            ans2.push_back({a[j], j});
        }
    }
    sort(ans2.begin(), ans2.end());
    for (auto &i : ans2) {
        ans.push_back(i.second);
    }
    for (int j = 0; j < n; j++) {
        if (!(ans_mask & (1 << j))) {
            ans.push_back(j);
        }
    }
    return ans;
}
// int main() {
//     for (int n = 2; n <= 25; n += 2) {
//         vector<int> a;
//         // set<int> all;
//         for (int j = 1; j <= n; j++) {
//             a.push_back(min(j, n - j + 1) * 2);
//         }
//         // long long at_least = (n * (n + 1) / 2 + 1) / 2, cnt = 0, sm = 0;
//         // for (auto k : solve(a)) {
//         //     all.insert(k);
//         // }
//         // if (all.size() != n || *all.rbegin() != n - 1 || *all.begin() != 0) {
//         //     throw(0);
//         // }
//         for (auto k : solve(a)) {
//             cout << min(k + 1, n - k) << " ";
//         }
//         cout << endl;
//         // for (auto k : solve(a)) {
//         //     cout << k << " ";
//         // }
//         // cout << endl;
//         // cout << cnt << " " << n << endl;
//         // if (cnt != n / 2 && n % 2 == 0) {
//         //     cout << "BAD " << n << endl;
//         //     throw(0);
//         // }
//         // if (cnt != n / 2 && cnt != (n + 1) / 2 && n % 2 == 1) {
//         //     cout << "BAD " << n << endl;
//         //     throw(0);
//         // }

//     }
// }