#include "partition.h"
#include <vector>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#include <algorithm>

using namespace std;

using ll = long long;

constexpr int MAXN = 2000000;
constexpr int MAXBULAN = 15;

int n, v[MAXN+2], p[MAXN+2];
vector<int> rs[(1<<MAXBULAN)];
bool preproc = false;

void radixSort(int maxi)
{
	const int BULAN = ((32 - __builtin_clz(maxi)) + 1) / 2;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < n; j++) {
			rs[(v[p[j]] >> (i*BULAN)) & ((1 << BULAN) - 1)].push_back(p[j]);
		}
		int nr = 0;
		for (int j = 0; j < (1<<BULAN); j++) {
			for (auto x : rs[j]) {
				p[nr++] = x;
			}
			rs[j].clear();
		}
	}
}

vector<signed> solve(vector<signed> A) {
	if (!preproc) {
		for (int i = 0; i < (1 << MAXBULAN); i++) {
			rs[i].reserve(512);
		}
		preproc = true;
	}
    n = A.size();
    ll total = 0;
    int maxi = 0;
	for (int i = 0; i < n; i++) {
		v[i] = A[i];
		maxi = max(maxi, v[i]);
		p[i] = i;
		total += v[i];
	}
	radixSort(maxi);
	ll suma = 0;
	int st = (n+1)/2, dr = 0;
	for (int i = 0; i < st; i++) {
		suma += v[p[i]];
	}
	while (2*suma < total) {
		st--;
		suma -= v[p[st]];
		dr++;
		suma += v[p[n-dr]];
	}
	vector<int> ansvec;
	for (int i = 0; i < st; i++) {
		ansvec.push_back(p[i]);
	}
	for (int i = 0; i < dr; i++) {
		ansvec.push_back(p[n-dr+i]);
	}
	for (int i = st; i < n-dr; i++) {
		ansvec.push_back(p[i]);
	}
	return ansvec;
}
