7749: BZOJ3749：[POI2015]Lasuchy

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

输入格式

第一行一个整数n(2<=n<=1000000)，表示食物的数量（即人数）。食物和人都从1~n编号。 第二行包含n个整数c[1],c[2],…,c[n](1<=c[i]<=10^9)。 假设第i个人(1<=i<n)左边是第i份食物，右边是第i+1份食物；而第n个人左边是第n份食物，右边是第1份食物。

输出格式

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

样例输入

5
5 3 7 2 9

样例输出

2 3 3 5 1

提示

题目来源

鸣谢Jcvb提供译文，Claris提供SPJ