题目描述

圆桌上摆放着 $n$ 份食物，围成一圈，第 $i$ 份食物所含热量为 $c_i$。相邻两份食物之间坐着一个人，共有 $n$ 个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。 假如某个人改变自己的选择后（其他 $n-1$ 个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。请你给每个人指定应该吃哪一份食物，使得所有人都能够满意。

输入格式

第一行一个整数 $n$，表示食物的数量（即人数，食物和人都从 $1\sim n$ 编号）。
第二行包含 $n$ 个整数 $c_1,c_2,\dots,c_n$。这里约定，第 $i$（$1\le i<n$）个人左边是第 $i$ 份食物，右边是第 $i+1$ 份食物；而第 $n$ 个人左边是第 $n$ 份食物，右边是第 $1$ 份食物。

输出格式

如果不存在这样的方案，仅输出一行 NIE。
如果存在这样的方案，输出一行共 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人选择的食物的编号。如果有多组这样的方案，输出任意一个即可。

5
5 3 7 2 9

2 3 3 5 1

提示

【数据范围】

对于所有数据，$2\leqslant n\leqslant 10^6$，$1\leqslant c_i\leqslant 10^9$。

原题名称：Łasuchy

感谢 @KSkun 为本题提供 SPJ。