#include "partition.h"
#include<vector>
#include<iostream>
#include<map>
#include<set>
using namespace std;
std::vector<int> solve(std::vector<int> a) {
    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;
    for (int i = 1; i < (1 << n); i++) {
        int mx = -1;
        long long sm = 0, cnt = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                cnt++;
                sm += a[j];
                mx = max(mx, a[j]);
            }
        }
        if (sm - mx >= (sm_all + 1) / 2 || sm < (sm_all + 1) / 2) {
            continue;
        }
        if (mn_ans > abs(n - 2 * cnt)) {
            mn_ans = abs(n - 2 * cnt);
            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 (long long n = 1; n <= 25; n++) {
//         vector<int> a;
//         // set<int> all;
//         for (int j = 1; j <= n; j++) {
//             a.push_back((1 << j));
//         }
//         // 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 << (1 << 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);
//         // }

//     }
// }