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

using namespace std;

using ll = long long;

constexpr int MAXN = 2000000;

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

void flip()
{
	ll suma = 0;
	for (int i = 0; i < n/2; i++) {
		suma = suma + v[p[i]] - v[p[i+n/2]];
	}
	if (suma > 0) {
		for (int i = 0; i < n/2; i++) {
			swap(p[i], p[i+n/2]);
		}
	}
}

int getMax()
{
	int maxi = 0, best = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] > maxi) {
			maxi = v[i];
			best = i;
		}
	}
	return best;
}

int getMaxViz()
{
	int maxi = 0, best = 0;
	for (int i = 0; i < n; i++) {
		if (viz[i] && v[i] > maxi) {
			maxi = v[i];
			best = i;
		}
	}
	return best;
}

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];
	}
	ll suma = 0;
	if (n%2==1) {
		int maxi = getMax();
		swap(p[maxi], p[n-1]);
		suma += v[maxi];
		viz[maxi] = true;
	}
	flip();
	for (int i = 0; i < n/2; i++) {
		suma += v[p[i]];
		viz[p[i]] = true;
	}
	for (int i = 0; 2*suma < total; i++) {
		viz[p[i]] = false;
		viz[p[i+n/2]] = true;
		suma = suma - v[p[i]] + v[p[i+n/2]];
	}
	vector<int> ansvec;
	int best = getMaxViz();
	for (int i = 0; i < n; i++) {
		if (viz[i] && i != best) {
			ansvec.push_back(i);
		}
	}
	ansvec.push_back(best);
	for (int i = 0; i < n; i++) {
		if (!viz[i]) {
			ansvec.push_back(i);
		}
	}
	fill(viz, viz+n, false);
	return ansvec;
}
