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

int _n, sum, res;
vector<pair<int, int>> V;
map<int, vector<int>> mp;
vector<int> ans, A;
set<int> st;

int calc(vector<int> ind) {
    int S = 0, T = (sum + 1) / 2;
    int i;
    for (i = 0; i < _n; i++) {
        S += A[ind[i]];
        if (S >= T)
            break;
    }
    // cerr << i << endl;
    int j = _n - i;
    return abs(i - j);
}

void systemd() {
    res = _n + 1;
    sum = 0;
    V.resize(_n);
    mp.clear();
}

void solve1() {
    for (const auto &[l, r] : mp) {
        for (int i = 0; i < (r.size() / 2); i++) {
            ans.push_back(r[i]);
            st.erase(r[i]);
        }
    }
}

void solve2() {
    for (int bit = 0; bit < (1 << _n); bit++) {
        vector<int> cur;
        for (int i = 0; i < _n; i++) {
            if ((1 << i) & bit) {
                cur.push_back(i);
            }
        }
        sort(cur.begin(), cur.end(), [&](int l, int r) {
            return A[l] < A[r];
        });
        for (int i = 0; i < _n; i++) {
            if (!((1 << i) & bit)) {
                cur.push_back(i);
            }
        }
        // cerr << res << ' ' << calc(cur) << endl;
        if (calc(cur) <= res) {
            res = calc(cur), ans = cur;
        }
    }
}

std::vector<int> solve(std::vector<int> A_) {
    _n = A_.size();
    systemd();
    A = A_;
    for (int &a : A)
        sum += a;
    for (int i = 0; i < _n; i++) {
        st.insert(i);
        mp[A_[i]].push_back(i);
        V[i] = {A_[i], i};
    }
    solve2();
    // cerr << res << endl;
    // cerr << "Sa: " << calc({5, 8, 6, 7, 0, 1, 2, 3, 4}) << endl;
    return ans;
}

/*
1
4
2 6 4 4
 */
