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

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

using namespace std;

using ll = long long;

constexpr int MAXN = 2000000;
constexpr int BULAN = 10;

int n, v[MAXN+2], p[MAXN+2];
vector<int> rs[(1<<BULAN)];

void radixSort(int maxi)
{
	for (int i = 0; (maxi >> (i*BULAN)); 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) {
    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];
	}
	/*
	if (n <= (1 << (BULAN+1))) {
		sort(p, p+n, [&](int i, int j) { return v[i] < v[j]; });
	}
	else {
		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;
}
