//#include "infection.h"
//#include <utility>
#include "partition.h"
//#include <pch.h>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <ios>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>

#define FASTIO ios_base::sync_with_stdio(0);cin.tie(NULL);
#define vec vector<int>
#define pii pair<int,int>
#define vecl vector<long long>
#define sz size()
#define endl '\n'
#define pll pair<long,long>
#define ff first
#define ss second
#define pshb push_back
using ll = long long;


using namespace std;

vec solve(vec v) {
	int n = v.sz;
	if (n <= 7) {
		ll sum = 0;
		for (int i = 0; i < n; i++)sum += v[i];
		int mn = n;
		//cout << "??" << sum << endl;
		vec ans(n);
		for (int i = 0; i < (1 << n); i++) {
			vector<pii> cur;
			for (int j = 0; j < n; j++) {
				if ((1 << j)&i) {
					cur.pshb({ v[j],j });
				}
			}
			for (int j = 0; j < n; j++) {
				if (!((1 << j)&i)) {
					cur.pshb({ v[j],j });
				}
			}
			ll curs = 0;
			for (int j = 0; j < n; j++) {
				curs += cur[j].ff;
				if (curs >= (sum + 1) / 2) {
					int qan = abs(j + 1 - (n - (j + 1)));
					if (qan < mn) {
						mn = qan;
						for (int z = 0; z < n; z++)ans[z] = cur[z].ss;
					}
					break;
				}
			}
		}
		//cout << "??" << mn << endl;
		return ans;
	}
	else {
		ll sum = 0;
		for (int i = 0; i < n; i++)sum += v[i];
		int mn = n;
		vector<pii> x(n);
		for (int i = 0; i < n; i++)x[i] = { v[i],i };
		//sort(x.rbegin(), x.rend());
		//cout << "??" << sum << endl;
		vec ans(n);
		for (int i = 8; i < (1 << n) / 8; i++) {
			vector<pii> cur;
			for (int j = 0; j < n; j++) {
				if ((1 << j)&i) {
					cur.pshb({ x[j].ff,j });
				}
			}
			for (int j = 0; j < n; j++) {
				if (!((1 << j)&i)) {
					cur.pshb({ x[j].ff,j });
				}
			}
			ll curs = 0;
			for (int j = 0; j < n; j++) {
				curs += cur[j].ff;
				if (curs >= (sum + 1) / 2) {
					int qan = abs(j + 1 - (n - (j + 1)));
					if (qan < mn) {
						mn = qan;
						for (int z = 0; z < n; z++)ans[z] = x[cur[z].ss].ss;
					}
					break;
				}
			}
		}
		//cout << "??" << mn << endl;
		return ans;
	}
}
