#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();
    ll S = accumulate(A.begin(),A.end(),0LL);
    bool is_rev = 0;
    if(accumulate(A.begin(),A.begin()+N/2,0LL) > S/2) is_rev = 1, reverse(A.begin(),A.end());
    vl P(N + 1,0);
    for(int i = 0;i < N;i++) P[i+1] = P[i] + A[i];
    for(int i = 0,j = N/2;;i++) {
        while(P[j+1] - P[i] < (S+1)/2) j++;
        if(j - i + 1 == (N+1)/2) {
            vi Ans;
            if(is_rev){
                i = N-1 - i;
                for(;Ans.size() < N;i = (i+N-1)%N) Ans.push_back(i);
            }
            else{
                for(;Ans.size() < N;i = (i+1)%N) Ans.push_back(i);
            }
            return Ans;
        }
    }
    return {};
}
