#include "partition.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <queue>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using pii = pair<int, int>;

constexpr int MAXN = 2000000;

int n, v[MAXN+2], p[MAXN+2];

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];
	}
	sort(p, p+n, [&](int i, int j)
	{
		return v[i] < v[j];
	});
	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;
}
