在今年 Byteotian 甜点爱好者聚会的晚宴结束时，$n$ 位贪食者围坐在一张圆桌旁。随后，桌上摆放了 $n$ 块蛋糕。这些蛋糕在大小、外观和口味上各不相同，但对于这些美食家来说，最重要的是它们的热量值（第 $i$ 块蛋糕的热量为 $c_i$）。餐桌的布置方式使得每相邻两位贪食者之间都有一块蛋糕。每位贪食者可以选择身边的两块蛋糕中的任意一块。如果一块蛋糕只有一位贪食者认领，那么它就完全属于该贪食者。然而，如果一块蛋糕被两位贪食者同时认领，他们必须平分这块蛋糕。

每位贪食者都希望最大化他们从所选蛋糕中获得的热量值（如果只分到一半，热量值减半）。如果贪食者做出了错误的选择，即如果他们选择另一块蛋糕能获得更多热量（假设其他人不改变决定），他们就会感到不满。请帮助贪食者做出选择，使得他们中没有任何人感到不满。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 1\,000\,000$)，表示贪食者（以及蛋糕）的数量。第二行包含一个由 $n$ 个整数组成的序列 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 1\,000\,000\,000$)，以空格分隔；第 $i$ 块蛋糕的热量值为 $c_i$。我们假设第 $i$ 位贪食者（对于 $1 \le i < n$）可以选择第 $i$ 块或第 $i+1$ 块蛋糕，而第 $n$ 位贪食者可以选择第 $n$ 块或第 $1$ 块蛋糕。

有一组测试数据占总分的 50%，其中 $n \le 1000$；其中一个子集占总分的 20%，满足 $n \le 20$。

输出格式

如果贪食者无法做出选择使得每一位都感到满意，则标准输出的第一行应输出单词 NIE（波兰语中的“不”）。否则，标准输出的第一行应输出一个由 $n$ 个整数组成的序列，以空格分隔；其中第 $i$ 个整数表示第 $i$ 位贪食者选择的蛋糕编号。如果存在多个正确答案，程序可以任意输出其中一个。

样例

输入 1

5
5 3 7 2 9

输出 1

2 3 3 5 1

说明

样例测试：

1ocen：$n = 20$，每块奇数编号的蛋糕热量值为 7，每块偶数编号的蛋糕热量值为 3；如果每位贪食者都选择热量值为 7 的蛋糕，那么每个人都会感到满意。

2ocen：$n = 1\,000\,000$，每块蛋糕的热量值在 $[500\,000\,001, 1\,000\,000\,000]$ 范围内随机选择；如果每位贪食者都选择他们右侧的蛋糕，或者每位贪食者都选择他们左侧的蛋糕，那么每个人都会感到满意。