#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include "partition.h"

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const ll INF = 1e18;

std::vector<int> solve(std::vector<int> a) {
    int n = (int) a.size();
    a.resize(2 * n);
    for (int i = 0; i < n; i++) {
        a[i + n] = a[i];
    }
    a.insert(a.begin(), 0);
    std::vector<ll> sum(2 * n + 1, 0);

    for (int i = 1; i <= 2 * n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }

    ll S = sum[n];

    int len = (n + 1) / 2;
    
    int found = -1;

    for (int i = n + 1; i <= 2 * n; i++) {
        if (sum[i] - sum[i - len] >= (S + 1) / 2 && sum[i - 1] - sum[i - len] < (S + 1) / 2) {
            found = i;
        }   
    }

    assert(found != -1);

    std::vector<int> answer(n);

    for (int i = 0; i < n; i++) {
        answer[i] = (found + i + n - 1) % n;
    }
    
    return answer;
}