H - 新入生歓迎数列 - Hard

Time Limit: 3 sec / Memory Limit: 256 MB

配点: 1000

問題文

パ研の新入生の PAKEN 君は, 長さ N の数列 P = {P_1, P_2, P_3, ..., P_N} を E869120 からもらった. 最初 P のすべての要素は 0 である.

PAKEN 君は, 数列 P に以下の操作を好きな順番で, 合計で 550 \ 000 回以内行うことによって, この数列を A = {A_1, A_2, A_3, ..., A_N} と同じにしようと思った.

  • 操作 1: 1 以上 N 以下の整数 x を選び, P_x の値を 1 に変更する.
  • 操作 2: 1 以上 N 以下の整数 y, z を選び, P_y の値に P_z の値を足す. ただし, y = z であってもよい. また, P_y の値は 10^{18} を超えてはならない.

PAKEN 君はまだ幼いので, どのような手順で操作をすればよいのか分からない. 彼を助けるために, あなたは操作の手順の一例を示さなければならない.


入力

入力は, 以下の形式で標準入力から与えられる.

N
A_1 A_2 A_3 ... A_N

出力

出力は, 以下の形式で標準出力から行うこと.

Q
(1 回目の操作の情報)
(2 回目の操作の情報)
(3 回目の操作の情報)
...
(Q 回目の操作の情報)

まず最初に, 行う操作の回数 Q を出力しなければならない. Q0 以上 550 \ 000 以下の整数でなければならない. 次の Q 行, 各回の操作の情報は, 以下のように出力しなければならない.

(☆) 操作 1 を行う場合

1 x

これは, P_x1 にするという操作を行う, という意味である.


(★) 操作 2 を行う場合

2 y z

これは, P_yP_z の値を足すという操作を行う, という意味である.

制約

  • N2 以上 200 \ 000 以下の整数である.
  • A_1 = 1 を満たす.
  • A_i (1 \leq i \leq N)1 以上 2^{30} - 1 以下の整数である.

小課題

小課題1 [ 60点 ]

  • N = 2 を満たす.

小課題2 [ 140点 ]

  • N \leq 8 \ 000 を満たす.

小課題3 [ 80点 ]

  • N \leq 16 \ 000 を満たす.

小課題4 [ 230点 ]

  • N \leq 25 \ 000 を満たす.

小課題5 [ 270点 ]

  • N \leq 160 \ 000 を満たす.

小課題6 [ 220点 ]

    追加の制約はない.

入力例1

2
1 4

出力例1

4
1 1
1 2
2 2 2
2 2 2

操作によって, 数列の値は {0, 0} -> {1, 0} -> {1, 1} -> {1, 2} -> {1, 4} というように変わる.

入力例2

3
1 3 5

出力例2

8
1 1
2 1 1
2 3 1
1 1
2 1 2
2 2 1
2 3 1
1 1

操作によって, 数列の値は {0, 0, 0} -> {1, 0, 0} -> {2, 0, 0} -> {2, 0, 2} -> {1, 0, 2} -> {3, 0, 2} -> {3, 3, 2} -> {3, 3, 5} -> {1, 3, 5} というように変わる.

writer: E869120