题目描述

题目译自 XXII Olimpiada Informatyczna — I etap Łasuchy

在字节城甜品爱好者聚会的盛大晚宴上，$n$ 个贪吃鬼围坐在圆桌旁，桌上摆放着 $n$ 个蛋糕。每个蛋糕的大小、模样和口味各异，但对贪吃鬼们来说，最重要的是蛋糕的热量（第 $i$ 个蛋糕热量为 $c_{i}$）。蛋糕摆放得恰到好处，每两个相邻的贪吃鬼之间有一个蛋糕。每个贪吃鬼可以选择吃左边或右边的蛋糕。若两人选了同一个蛋糕，就平分它。

每个贪吃鬼都想最大化自己吃到的蛋糕（或半块蛋糕）的热量。如果发现选错了——即选另一块蛋糕能吃到更多热量（假设其他贪吃鬼的选择不变），他就会不满意。请你帮助贪吃鬼们选择蛋糕，确保没人感到遗憾。

输入格式

输入第一行包含一个整数 $n$ $(2 \leq n \leq 1000000)$，表示贪吃鬼（及蛋糕）的数量。

第二行包含 $n$ 个整数 $c_{1}, c_{2}, \ldots, c_{n}$ $(1 \leq c_{i} \leq 1000000000)$，$c_{i}$ 表示第 $i$ 个蛋糕的热量。

假设第 $i$ $(1 \leq i < n)$ 个贪吃鬼可选择第 $i$ 或 $i+1$ 个蛋糕，第 $n$ 个贪吃鬼可选择第 $n$ 或第 $1$ 个蛋糕。

输出格式

若无法让所有贪吃鬼都满意，输出一行 NIE。

否则，输出一行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个贪吃鬼选择的蛋糕编号。若有多组解，输出任意一组即可。

5
5 3 7 2 9

2 3 3 5 1

附加样例

1. $n=20$，奇数编号蛋糕热量为 $7$，偶数编号蛋糕热量为 $3$，每个贪吃鬼选热量为 $7$ 的蛋糕可满意；
2. $n=1000000$，每个蛋糕热量为 $[500000001, 1000000000]$ 内的随机数，若所有贪吃鬼都选右侧或左侧蛋糕，每人都满意。

数据范围与提示

对于 $50\%$ 的数据，$n \leq 1000$。
对于其中 $20\%$ 的数据，$n \leq 20$。