#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "partition.h"

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ar array
#define int long long
#define all(v) v.begin(), v.end()

const int N = 1e5 + 20;
const int MOD = 1e9 + 7;
const int INF = 1e16;

template<typename T>
void chmin(T &a, T b){a = min(a, b);};
template<typename T>
void chmax(T &a, T b){a = max(a, b);};
template<typename T>
void mm(T &x){
    x %= MOD;
    if (x < 0) x += MOD;
};

std::vector<signed> solve(std::vector<signed> arr) {
    int n = arr.size();
    int LIM = 0;
    for (auto u: arr)LIM += u;
    LIM = (LIM + 1) / 2;
    map<int,int> dp[n + 1];
    dp[0][0] = -1;
    vector<ar<int,2> > A(n);
    for (int i = 0;i < n;i++)A[i] = {arr[i], i};
    sort(all(A));
    for (int i = 0;i < n;i++) {
        for (auto [a, b]: dp[i]) {
            if (a + A[i][0] < LIM)dp[i + 1][a + A[i][0]] = i;
            dp[i + 1][a] = b;
        }
    }
    auto [a, b] = *dp[n].rbegin();
    set<int> s;
    int i = b;
    int sum = a;
    while (i != -1) {
        s.insert(A[i][1]);
        sum -= A[i][0];
        i = dp[i][sum];
    }
    vector<signed> ans;
    for (int i = 0;i < n;i++) {
        if (s.find(i) == s.end())ans.push_back(i);
    }
    for (auto u: s)ans.push_back(u);
    return ans;
}


#define int signed