#include<vector>
#include<iostream>
#include<algorithm>
#include"partition.h"
using namespace std;
using ll = long long;
std::vector<int> solve(std::vector<int> A) {
	int n = A.size();
	int mn = 1e9, mx = 0, s = 0;
	vector<pair<int,int>>v;
	for (int i = 0; i < n; i++) {
		mx = max(mx, A[i]);
		v.push_back({ A[i],i });
		s += A[i];
	}
	sort(v.begin(), v.end());
	int l = -1, f = -1;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = i; j < n; j++) {
			sum += v[j].first;
			if (sum < (s + 1) / 2 && sum + mx >= (s + 1) / 2 && j != n - 1) {
				int araj = abs((j - i + 1+1) - (n - (j - i + 2)));
				if (araj < mn) {
					mn = araj;
					l = i;
					f = 1;
				}
			}
			else if (sum >= s) {
				int araj = abs((j - i + 1) - (n - (j - i + 1)));
				if (araj < mn) {
					mn = araj;
					l = i;
					f = 0;
				}



				break;
			}
		}
	}
	//cout << mn << " " << f << " " << l << endl;
	vector<int>ans;
	if (f == 1) {
		int sum = 0, r = 0;
		for (int j = l; j < n; j++) {
			ans.push_back(v[j].second);
			sum += v[j].first;
			if (sum < (s + 1) / 2 && sum + mx >= (s + 1) / 2 && j != n - 1) {
				r = j;
				break;
			}
			
		}
		ans.push_back(v[n - 1].second);
		for (int j = 0; j < n; j++) {
			if (j < l || (j > r && j < n - 1)) {
				ans.push_back(v[j].second);
			}
		}
	}
	else {
		int sum = 0, r = 0;
		for (int j = l; j < n; j++) {
			ans.push_back(v[j].second);
			sum += v[j].first;
			if (sum >= (s + 1) / 2) {
				r = j;
				break;
			}

		}
		for (int j = 0; j < n; j++) {
			if (j < l || (j > r )) {
				ans.push_back(v[j].second);
			}
		}
	}
		

	
	return ans;
	
}
