#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(),L = (N+1)/2;
    ll curr = accumulate(A.begin(),A.begin() + L,0LL);
    ll S = accumulate(A.begin(),A.end(),0LL);
    for(int i = 0;1;i++){
        if(curr >= (S+1)/2 && curr - A[i+L-1] < (S+1)/2) {
            vi B(N);
            for(int q = 0;q < N;q++,i++) B[q] = i % N;
            return B;
        }
        if(i + L >= N) break;
        curr -= A[i];
        curr += A[i+L];
    }
    for(int i = N-1;1;i--){
        if(curr >= (S+1)/2 && curr - A[i-L+1] < (S+1)/2) {
            vi B(N);
            i += N;
            for(int q = 0;q < N;q++,i--) B[q] = i % N;
            return B;
        }
        if(i - L < 0) break;
        curr -= A[i];
        curr += A[i-L];
    }
    return {};
}
