#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
vi solve(vi A) {
    int N = A.size();
    vl P(N + 1,0);
    for(int i = 0;i < N;i++) P[i+1] = P[i] + A[i];
    ll S = P.back();
    for(int i = 0,j = 0;;i++) {
        while(P[j+1] - P[i] < (S+1)/2) j++;
        if(j == N-1) break;
        if(j - i + 1 == (N+1)/2) {
            vi Ans(N);
            for(int q = 0;q < N;q++,i = (i+1)%N) Ans[q] = (i);
            return Ans;
        }
    }
    for(int i = N-1,j = N-1;;i--) {
        while(-(P[j] - P[i+1]) < (S+1)/2) j--;
        if(j == 0) break;
        if(-(j - i) + 1 == (N+1)/2) {
            vi Ans(N);
            for(int q = 0;q < N;q++,i = (i+N-1)%N) Ans[q] = (i);
            return Ans;
        }
    }
    return {};
}
