B： 階層的計算機 (Hierarchical Calculator)

問題

N 個の 1 次式 y = a_i x (1 \leq i \leq N) が与えられます。

1, 2, ..., N の部分列 s_1, s_2, ..., s_k (i < j ならば s_i < s_j) を考えます。まず式 s_1 を x = 1 として評価することから始め、式 s_i を評価した結果を式 s_{i+1} に x として入力することを考えます。すなわち以下のようになります。

• x_0 = 1
• x_i = a_{s_i} x_{i-1} (1 \leq i \leq k)

このとき、x_k が最大となるような部分列を求めてください。ただし、そのような部分列が複数考えられる場合は列の長さが最小のものを求めるとします。また、さらにそのような部分列が複数考えられる場合は辞書順最小のものを求めるとします。ただし、部分列 s_1, s_2, ..., s_m が t_1, t_2, ..., t_n より辞書順で小さいとは以下のいずれかの場合を指します。

• ある i が存在して s_1=t_1, s_2=t_2, ..., s_i=t_i かつ s_{i+1}<t_{i+1}
• m<n で、s_1=t_1, s_2=t_2, ..., s_m=t_m

入力形式

N
a_1 a_2 $\cdots$ a_N

制約

• 1 \leq N \leq 60
• -2 \leq a_i \leq 2
• 入力は全て整数

出力形式

1 行目には部分列の長さ k を出力してください。 1+i 行目には部分列の i 番目、すなわち s_i を出力してください。

入力例1

4
2 0 -2 1

出力例1

1
1

式 1 のみを評価して最大値 2 を得ます。式 4 を評価する必要はありません。

入力例2

3
2 -2 -2

出力例2

3
1
2
3

全ての式を評価して最大値 8 を得ます。

入力例3

2
-1 0

出力例3

0

何も評価せず最大値 1 を得ます。空列は全ての列の中で個数最小かつ辞書順最小です。

入力例4

5
-1 2 1 -2 -1

出力例4

3
1
2
4

最大値は 4 です。$\langle$ 2, 4, 5 $\rangle$ は辞書順最小ではありません。

Note

Link

 

---