#include "partition.h"
#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 emplace_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 = 30, N = 2e6, MX = 1e9;
static int a[N];

vc<int> solve(vc<int> b) {
	int n = b.size(), ptr = 0;
	int bl = 1e4, sz = MX / bl;
	
	int lim = sqrt(n) + 1;
	vc<vc<int>> id (sz + 1);
	for (int i = 0; i < n; i++) id[b[i] / bl].pb(i);
	for (int i = 0; i <= sz; i++) {
		if (id[i].empty()) continue;
		
		if (id[i].size() < 1e4) {
			sort(all(id[i]), [&](int l, int r){
				return b[l] < b[r];
			}); for (int j : id[i]) a[ptr++] = j;
		} else {
			int st = i * bl;
			vc<vc<int>> cnt (bl);
			for (int j : id[i]) cnt[b[j] - st].pb(j);
			for (int x = 0; x < bl; x++) for (int j : cnt[x]) a[ptr++] = j;
		}
		
	}
		
	ll t = 0;
	for (int i = 0; i < n; i++) t += b[i];
	t = (t + 1) / 2;
	
	int i = 0;
	ll sum = 0;
	for (; i < n && sum < t; i++) sum += 1ll * b[a[i]];
	
	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 = b[a[r]] - b[a[l]];
			swap(a[r--], a[l++]);
			sum += d;
		} sum -= b[a[--i]];
	}
	
	i++;
	l = i;
	int cur = 0;
	for (int j = 0; j + 1 < i; j++) if (b[a[j]] < b[a[j + 1]]) l = j;
	
	for (int j = l; j < i; j++) b[cur++] = a[j];
	for (int j = l - 1; j >= 0; j--) b[cur++] = a[j];
	
	for (int j = i; j < n; j++) b[cur++] = a[j];
	
	return b;
}