RT：

题目描述

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

输入格式

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

输出格式

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

说明/提示

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

感谢 @KSkun 为本题提供 SPJ。

源码：

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

## 输入格式 

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

## 输出格式 

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

## 说明/提示 

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

感谢 @KSkun 为本题提供 SPJ。