太陽系外惑星にある島は、一年を通して多くのカモメに似た鳥（以下、単にカモメと呼ぶ）を観察できるバードウォッチングのスポットとして有名である。その惑星は地球と非常によく似ているが、一年の日数が異なっている。

各カモメは一年に一度だけ島に飛来し、しばらく滞在した後、一年に一度だけ島を去る。各カモメには独自の飛来日と離去日のスケジュールがあり、非常に正確にそのスケジュールを守る。つまり、毎年同じ日に島に飛来し、毎年同じ日に島を去る。カモメは早朝に島に飛来し、夕方に島を去る。島に飛来したカモメが同じ日に去ることもある。一方で、ある日に島を去り、翌日に再び飛来するカモメもいる。

バードウォッチングクラブのメンバーは、毎日正午頃に島に滞在しているカモメの数を数えている。彼らのカウントは完璧であり、その時点で島にいるすべてのカモメが漏れや重複なく数えられる。しかし、カモメは見た目が非常に似ているため、個体を識別することは不可能である。

ある日の夕方に島を去り、翌日の朝に再び飛来するカモメは、一年中のすべての日にカウントされることに注意せよ。

一年を通した毎日のカモメのカウント数が与えられたとき、島を訪れるカモメの総数を知りたい。カモメは識別できないため、正確な数を知ることはできない。例えば、2日連続でカウントが1であった場合、カモメの数は1羽かもしれないし、2羽かもしれない。得られる唯一の有益な情報は、最小の可能性のある数である。

一年間に少なくとも一度はカウントされる個々のカモメの最小の可能性のある数を求めよ。もしこの最小値が十分に小さい場合は、その最小値を達成する滞在期間のリストも提示せよ。

入力

入力は以下の形式の単一のテストケースからなる。

$n$ $b_1 \ b_2 \ \dots \ b_n$

整数 $n$ ($2 \le n \le 2 \times 10^5$) は、その惑星における一年の日数である。日は一年を通して $1$ から $n$ まで番号が付けられている。整数 $b_i$ ($0 \le b_i \le 2 \times 10^5$) は、$i$ 日目にカウントされたカモメの数である。$b_i$ のうち少なくとも一つは非ゼロである。

出力

1行目に、カモメの最小の可能性のある数 $m$ を出力せよ。もし $m$ が $2 \times 10^5$ 以下であれば、続けて $m$ 行を出力し、滞在期間のリストを一つ提示せよ。これらの $m$ 行のうち $j$ 番目の行には、スペースで区切られた2つの整数 $s_j$ と $t_j$ ($1 \le s_j \le n, 1 \le t_j \le n$) を含めること。これは、$j$ 番目のカモメが $s_j$ 日目に島に飛来し、$t_j$ 日目に去ることを表す。$s_j$ が $t_j$ より大きくなる場合があることに注意せよ。その場合、カモメは一年の最後の日から翌年の最初の日まで、年をまたいで島に滞在していることを意味する。可能性が複数ある場合は、そのいずれを出力してもよい。

入出力例

入出力例 1

7
1 0 1 2 2 0 1

出力例 1

3
3 5
4 5
7 1

入出力例 2

2
1 1

出力例 2

1
1 2

入出力例 3

6
1 2 1 2 2 1

出力例 3

2
2 5
4 2

入出力例 4

4
200000 0 200000 0

出力例 4

400000

注記

以下の図は、出力例1における3羽のカモメの滞在スケジュールを描いたものである。3羽目のカモメは年をまたいで島に滞在していることに注意せよ。

図 C.1. 出力例1におけるカモメの滞在スケジュール