P3584 [POI 2015 R1] Gluttons

There are $n$ dishes placed around a round table, forming a circle. The $i$-th dish contains $c_i$ calories. Between every pair of adjacent dishes sits one person, so there are $n$ people in total. Each person can choose to eat either the dish on their left or the dish on their right. If two people choose the same dish, they split it equally, and each receives half of that dish’s calories. If a person can obtain strictly more calories than before by changing only their own choice (while the choices of the other $n-1$ people remain unchanged), then that person is dissatisfied. Please assign which dish each person should eat so that everyone is satisfied.

The first line contains an integer $n$, the number of dishes (which is also the number of people; both dishes and people are numbered from $1$ to $n$). The second line contains $n$ integers $c_1, c_2, \dots, c_n$. We stipulate that for person $i$ ($1 \le i < n$), the dish on the left is dish $i$, and the dish on the right is dish $i+1$; for person $n$, the dish on the left is dish $n$, and the dish on the right is dish $1$.

If no such assignment exists, output a single line NIE. If such an assignment exists, output one line with $n$ integers, where the $i$-th integer is the index of the dish chosen by person $i$. If multiple valid assignments exist, output any one of them.

Constraints For all testdata, $2 \leqslant n \leqslant 10^6$, $1 \leqslant c_i \leqslant 10^9$. ---- Original title: Łasuchy. Thanks to @KSkun for providing the SPJ for this problem. Translated by ChatGPT 5