#include "partition.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define speedup cin.tie(0) -> sync_with_stdio(0)
#define all(x) begin(x), end(x)
#define pb push_back
#define vc vector

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
template<class T> bool chmin(T &a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}

const int LG = 25;
vc<int> solve(vc<int> b) {
	int n = b.size();
	vc<array<ll, 2>> a (n);
	for (int i = 0; i < n; i++) a[i] = {b[i], i};
	
	ll t = 0ll;
	sort(all(a));
	for (auto [x, i] : a) t += 1ll * x;
	
	t = (t + 1) / 2;
	
	int i = 0;
	ll sum = 0;
	for (; i < n && sum < t; i++) sum += 1ll * a[i][0];
	
	int l = 0, r = n - 1;
	for (; i >= n / 2;) {
		if (l > r) break;
		if (l >= i) break;
		if (r < i - 1) break;
		
		while (sum < t) {
			if (l > r) break;
			int d = a[r][0] - a[l][0];
			swap(a[r--], a[l++]);
			sum += d;
		} sum -= a[--i][0];
	}
	
//	i++;
	vc<int> res;
	for (int j = l; j < i; j++) res.pb(a[j][1]);
	for (int j = l - 1; j >= 0; j--) res.pb(a[j][1]);
	for (int j = i; j < n; j++) res.pb(a[j][1]);
	return res;
}