#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;

int n, len, v[MAXN+2];
bool revd;

void flip()
{
	ll suma = 0;
	for (int i = 0; i < n/2; i++) {
		suma = suma + v[i] - v[i+len];
	}
	if (suma > 0) {
		reverse(v, v+n);
		revd = true;
	}
	else {
		revd = false;
	}
}

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

vector<signed> solve(vector<signed> A) {
    n = A.size();
    len = (n+1)/2;
    ll total = 0;
	for (int i = 0; i < n; i++) {
		v[i] = A[i];
		total += v[i];
	}
	flip();
	ll suma = 0;
	for (int i = 0; i < len; i++) {
		suma += v[i];
	}
	int st = 0;
	while (2*suma < total) {
		suma = suma - v[st] + v[st+len];
		st++;
	}
	vector<int> ansvec;
	for (int i = st; i < st+len; i++) {
		ansvec.push_back(i);
	}
	for (int i = 0; i < st; i++) {
		ansvec.push_back(i);
	}
	for (int i = st+len; i < n; i++) {
		ansvec.push_back(i);
	}
	if (revd) {
		for (auto &x : ansvec) {
			x = n-1-x;
		}
	}
	return ansvec;
}
