#include "partition.h"
#include <bits/stdc++.h>

using namespace std;
#define all(x) (x).begin(), (x).end()

using ll = long long;

int n;

inline int mdn(int x) {
	if (x == n) {
		return 0;
	}
	if (x == -1) {
		return n - 1;
	}
	return x;
}

vector<signed> solve(vector<signed> a) {
	n = a.size();
	ll sum = 0;
	for (auto &i : a) {
		sum += i;
	}
	sum = (1 + sum) / 2;
	ll sum1 = 0, sum2 = 0;
	for (int i = 0; i < (n - 1) / 2; i ++) {
		sum1 += a[i];
		sum2 += a[i];
	}
	sum2 += a[(n - 1) / 2];
	if (sum1 < sum && sum2 >= sum) {
		vector<signed> ans;
		for (int i = 0; i < n; i ++) {
			ans.push_back(i);
		}
		return ans;
	}
	int loc = 0;
	for (int i = (n + 1) / 2; i != (n - 1) / 2; i = mdn(i + 1)) {
		sum2 += a[i];
		sum1 += a[mdn(i - 1)];
		sum1 -= a[loc];
		sum2 -= a[loc];
		loc = mdn(loc + 1);
		if (sum1 < sum && sum2 >= sum) {
			vector<signed> ans;
			for (int j = loc; j != i; j = mdn(j + 1)) {
				ans.push_back(j);
			}
			for (int j = i; j != loc; j = mdn(j + 1)) {
				ans.push_back(j);
			}
			return ans;
		}
	}
	vector<signed> ans;
	for (int i = 0; i < n; i ++) {
		ans.push_back(i);
	}
	return ans;
}
