配点

満点

100

部分点1

20

部分点2

40

---

問題文

分数の真ん中の線分を括線(Vinculum)という。分数の計算時、短い括線から順に計算するという暗黙のルールがある。

N個の非$0$実数列$\\{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$は非$0$の実数で、整数部がちょうど$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$ 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは基本制約に加えて下記の制約も満たす。

• $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

---

Writer: uwi

---

Source Name

Autumn Fest

---