#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;


int n;

std::vector<int> solve(std::vector<int> A){
    n = A.size();
    long long sum = 0ll;
    for(int i = 0; i < n; ++i){
        sum += A[i];
    }
    //sort(a, a+n);
    int sz = (n+1)/2, idx = 0, gr = sz;
    if(gr == n) gr = 0;
    long long tmp = 0ll;
    for(int i = 0; i < sz; ++i) tmp += A[i];
    sum = (sum+1)/2;
    while(tmp > sum){
        //cout << idx << endl;
        tmp += A[gr] - A[idx];
        idx++;
        gr++;
        if(gr >= n) gr = 0;
        if(idx >= n){
            idx = 0;
            break;
        }
    }
    //cout << tmp << ' ' << sum << ' ' << idx << ' ' << gr << endl;
    while(tmp < sum){
        //cout << idx << endl;
        tmp += A[gr] - A[idx];
        idx++;
        gr++;
        if(gr >= n) gr = 0;
        if(idx >= n) idx = 0;
    }
    int id = 0;
    vector<int> r(n);
    //cout << idx << ' ' << id << endl;
    for(int i = idx;;){
        r[id] = i;
        ++id;
        ++i;
        if(i >= n) i = 0;
        if(id == n) break;
    }
    return r;
}
