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

const int N = 1e5 + 10;

int dp[2002][2002];
int lst[2002][2002];
pair<int, int> v[N];

std::vector<int> solve(std::vector<int> A) {
	int n = A.size();
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		v[i] = { A[i], i };
		sum += A[i];
	}
	sum = (sum + 1) / 2;
	sort(v, v + n);
	long long s = 0;
	vector<int> res;
	for (int i = 0; i < n; i++) {
		res.push_back(v[i].second);
	}
	for (int i = 0; i < (n + 1) / 2; i++) {
		s += v[i].first;
	}
	int l = (n + 1) / 2 - 1, r = n - 1;
	while (s < sum) {
		s -= v[l].first;
		s += v[r].first;
		swap(res[l], res[r]);
		l--, r--;
	}
	return res;
}
