配点

满分

100

部分分1

20

部分分2

40

---

题目描述

分数中间的线段称之为Vinculum。在计算分数时，有一个隐含规则是按照短括号的顺序进行计算。

给定N个非零实数的序列 $\\{a_N\\}$。将它们从上到下排成一列，并在它们之间引入长度为1至N-1的不同长度的括号，可以表示分数并表达出计算顺序。

例如，在以下图中，在1.0和2.0之间引入长度为3的括号，在2.0和3.0之间引入长度为1的括号，在3.0和4.0之间引入长度为2的括号，计算后结果为6.0。这种括号的引用方式实现了数列[ 1.0, 2.0, 3.0, 4.0 ]的最大值。

图1

按照短括号的计算顺序，求出能够使最终的数值最大化的括号长度序列。

输入格式

输入以以下格式给出：

$N\\\\ a_1\\ a_2\\ ...\\ a_N$

其中，N是数列的长度；$a_i$表示从上到下第i个数字。

输出格式

输出以以下格式给出：

$L_1\\\\ L_2\\\\ ...\\\\ L_{N-1}$

输出包含N-1个不同的整数，范围在1至N-1之间，每行一个数字。$L_i$表示$a_i$和$a_{i+1}$之间引入的括号长度。

当存在多个解时，任意输出一个即可。

约束条件

• $2 ≤ N ≤ 10000$
• $a_i$是非零实数，整数部分有且仅有1位小数部分有且仅有1位。即为$-9.9,-9.8,...-1.1,-1.0,-0.9,...-0.1,0.1,...,0.9,1.0,1.1,...,9.9$中的某一个。

题目的评测将包含20分、40分两组测试样例，这些测试样例除了基本约束外还具有以下约束：

20分测试样例：

• $2 ≤ N ≤ 9$

40分测试样例：

• $2 ≤ N ≤ 50$

输入样例1

4
1.0 2.0 3.0 4.0

输出样例1

3
1
2

为题目中的示例。

---

输入样例2

4
0.1 0.2 0.3 0.4

输出样例2

1
2
3

---

输入样例3

4
9.9 0.1 -9.9 -0.1

输出样例3

3
2
1

---

出题人：uwi

---

来源名称

秋季祭

---