問題文

$a=(A_{1}, A_{2}, \dots, A_{N})$ で初期化された非負整数列 $a$ があります。

また、$f(x,y)$ を次の条件を満たす非負整数 $k$ の最小値と定義します。
ただし、そのような値が存在しない場合は $f(x,y) = 0$ とします。

• $k$ 以上の任意の整数 $z$ に対してある非負整数の組 $(p,q)$ が存在し、$z = p x + q y$ が成り立つ。

これから、$a$ に対して次の操作を $N - 1$ 回行います。

• $1 \leq i, j \leq |a|$ かつ $i \neq j$ かつ $\boldsymbol{ f(a_{i}, a_{j}) \leq 10^{18} }$ を満たす整数の組 $(i, j)$ を $1$ 個選び、
  $a$ から $2$ 個の要素 $a_{i}, a_{j}$ を削除して末尾に $f(a_{i}, a_{j})$ を $1$ 個追加する。

  ただし、$a_{x}$ は $a$ の先頭から $x$ $(x \geq 1)$ 番目の要素を指し、「$a$ から $a_{x}$ を削除する」とは、
  $a$ から $a_{x}$ を取り除き、残った要素を順序を保ったまま列の先頭に向かって詰める操作を指す。

$N-1$ 回の操作終了後に $a$ に含まれるただ $1$ 個の要素としてあり得るものの最小値を求めてください。
なお、本問の制約下において、$N - 1$ 回の操作を行う方法が少なくとも $1$ つ存在することが証明できます。

下の「出力」の項に従い、答えを操作方法と合わせて出力してください。

制約

• $2 \leq N \leq 2 \times 10^{5}$

• $0 \leq A_{i} \leq 2 \times 10^{5}$ $(1 \leq i \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$

• $1$ 行目には $N$ が与えられる

• $2$ 行目には $A_{1}, A_{2}, \dots, A_{N}$ がこの順に半角スペース区切りで与えられる

出力

次の形式に従い、答えを $1$ 行ずつ合計 $N$ 行に出力してください。

$M$
$i_{1}$ $j_{1}$
$i_{2}$ $j_{2}$
   $\vdots$
$i_{N-1}$ $j_{N-1}$

まず、$1$ 行目には最終的に $a$ に含まれる要素の最小値 $M$ を出力してください。

続いて、$2, 3, \dots, N$ 行目には最終的に $a$ に含まれる要素が $M$ になるような $N-1$ 回の操作方法を出力してください。
$k+1$ $(1 \leq k \leq N-1)$ 行目には、$k$ 回目の操作で選ぶ整数の組 $(i, j) = (i_{k}, j_{k})$ を $i_{k}, j_{k}$ の順に半角スペース区切りで出力してください。

このとき、$k$ $(1 \leq k \leq N-1)$ 回目の操作を行う直前において、次の条件をすべて満たす必要があります。

• $1 \leq i_{k}, j_{k} \leq |a|$

• $i_{k} \neq j_{k}$

• $\boldsymbol{ f(a_{ i_{k} }, a_{ j_{k} }) \leq 10^{18} }$

出力が上記の要件のうち少なくとも $1$ つを満たさない場合、提出された解答は AC と判定されませんのでご注意ください。

なお、上記の要件をすべて満たす正しい解答が複数存在する場合、どれを出力しても AC と判定されます。

サンプル

2
3 5

8
1 2

8
2 1

2
100 100

0
1 2

6
173448 104807 158459 62861 173448 173448

0
1 5
4 5
2 3
1 3
1 2

0
1 5
5 2
3 4
1 2
2 1

0
1 2
5 1
1 4
3 1
1 2

3
199993 199997 199999

7999440010999938
1 2
1 2

7999440010999944
3 1
1 2