#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 = 1024;
constexpr int BULANCNT = 3;
constexpr int BULANPOW[BULANCNT] = {1, BULAN, BULAN*BULAN};

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

void radixSort()
{
	for (int i = 0; i < BULANCNT; i++) {
		for (int j = 0; j < n; j++) {
			rs[v[p[j]]/BULANPOW[i]%BULAN].push_back(p[j]);
		}
		int nr = 0;
		for (int j = 0; j < 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;
	for (int i = 0; i < n; i++) {
		v[i] = A[i];
		p[i] = i;
		total += v[i];
	}
	radixSort();
	ll suma = 0;
	for (int i = 0; i < (n+1)/2; i++) {
		suma += v[p[i]];
	}
	int st = (n+1)/2, dr = 0;
	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;
}
