一颗系外行星上的岛屿是一个著名的观鸟胜地，全年都可以看到许多长相酷似海鸥的鸟类（以下简称海鸥）。这颗行星与地球非常相似，但一年的天数不同。

每只海鸥每年恰好来到岛上一次，停留一段时间，然后每年恰好离开一次。每只海鸥都有自己固定的来去时间表，并且非常准时地遵守该时间表。也就是说，每年它都在同一天来到岛上，也在同一天离开。海鸥在清晨来到岛上，在傍晚离开。来到岛上的海鸥可能在同一天离开。另一方面，海鸥也可能在某一天离开，并在第二天再次来到岛上。

观鸟俱乐部的成员每天中午左右都会统计岛上海鸥的数量。他们的统计非常精确，因此当时在场的所有海鸥都被统计在内，没有遗漏或重复。然而，由于海鸥长得太像了，无法识别个体。

请注意，在某天傍晚离开并在第二天清晨再次来到岛上的海鸥，在一年中的每一天都会被统计到。

给定一年中每天的海鸥统计数量，你想要知道访问该岛的海鸥总数。由于海鸥无法区分，因此无法得知确切的数量。例如，如果连续两天的统计数量均为 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$ 中至少有一个非零值。

输出格式

在第一行输出海鸥的最小可能数量 $m$。如果 $m$ 不超过 $2 \times 10^5$，则额外输出 $m$ 行，描述一种可能的停留周期列表。这 $m$ 行中的第 $j$ 行应包含两个由空格分隔的整数 $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 中三只海鸥的访问时间表。请注意，第三只海鸥跨年停留在岛上。

图 C.1. 样例输出 1 中海鸥的访问时间表