这是一个关于摧毁废墟城市中建筑的双人电子游戏。游戏中，平地上有 $N$ 座建筑。建筑从左到右依次编号为 $1$ 到 $N$。第 $i$ 座建筑的高度为 $A_i$ ($1 \le i \le N$)，这是一个 $1$ 到 $N$ 之间的正整数。没有两座建筑的高度相同。

最初，两名玩家都位于所有建筑的左侧。在每一个整数时刻 $i (\ge 1)$，两名玩家同时各发射一枚子弹，子弹从发射位置向右水平飞行。两枚子弹的速度相同。玩家选择子弹的发射高度 $H$（即距离地面的高度）。高度 $H$ 是一个 $1$ 到 $N+1$ 之间的整数。两名玩家可以选择相同的高度。

如果一名玩家的子弹发射高度为 $H$，则满足 $A_i \ge H$ 且尚未被摧毁的最左侧建筑将被该子弹摧毁。如果没有建筑满足此条件，则什么也不会发生。如果两名玩家击中了同一座建筑，则只有该建筑被摧毁。例如，如果 $A_1 = 2, A_2 = 1$，且两名玩家最初都将 $H = 1$ 作为发射高度，则建筑 $1$ 将被摧毁，而建筑 $2$ 将保持原样。

给定 $N$ 座建筑的高度，求摧毁所有建筑所需的最短时间，并提供实现该目标的任意一组发射高度序列。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)。 下一行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le N$，所有 $A_i$ 互不相同)。

输出格式

第一行输出一个整数 $T$，表示最短时间。 接下来的 $T$ 行，每行输出两个整数，表示两名玩家的发射高度。两个整数均应在 $1$ 到 $N+1$ 之间。这两个整数可以相等。

样例

样例输入 1

8
4 3 8 2 1 7 6 5

样例输出 1

4
4 8
3 7
2 6
1 5

样例输入 2

8
5 6 7 1 2 8 3 4

样例输出 2

4
5 6
7 8
1 2
3 4

样例输入 3

4
1 2 4 3

样例输出 3

2
4 1
2 3