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

std::vector<int> solve(std::vector<int> A) {
	vector<vector<long long>> dp(A.size(), vector<long long>(A.size() + 1, 0));
	vector<pair<long long, int>> v;
	for (int i = 0; i < A.size(); i++) {
		v.push_back({ A[i], i });
	}
	sort(v.begin(), v.end());
	vector<vector<int>> lst(A.size(), vector<int>(A.size() + 1, -1));
	dp[0][0] = 0;
	dp[0][1] = A[0];
	lst[0][1] = 0;
	long long sum = 0;
	for (auto i : A) {
		sum += i;
	}
	for (int i = 1; i < A.size(); i++) {
		for (int j = 0; j <= A.size(); j++) {
			dp[i][j] = dp[i - 1][j];
			if (j > 0 && dp[i - 1][j - 1] < ((sum + 1) / 2)) dp[i][j] = dp[i - 1][j - 1] + A[i], lst[i][j] = i;
		}
	}
	int j = 0, mn = A.size() + 10;
	for (int i = 0; i <= A.size(); i++) {
		if (dp[A.size() - 1][i] >= (sum + 1) / 2) {
			if (mn > abs(i - ((int)A.size() - i))) {
				mn = abs(i - ((int)A.size() - i));
				j = i;
			}
		}
	}
	vector<int> res;
	int i = A.size() - 1;
	vector<bool> used(A.size(), 0);
	while (i >= 0 && j >= 0) {
		if (lst[i][j] == -1) {
			i--;
		}
		else {
			used[lst[i][j]] = 1;
			res.push_back(lst[i][j]);
			i--, j--;
		}
	}
	reverse(res.begin(), res.end());
	for (int i = 0; i < A.size(); i++) {
		if (!used[i]) {
			res.push_back(i);
		}
	}
	return res;
}
