409540: GYM103627 D Two Bullets

There is a two-person video game about destroying buildings in a ruined city. In the game, there are $$$N$$$ buildings over flat ground. Buildings are indexed from $$$1$$$ to $$$N$$$ from left to right. The height of building $$$i$$$ is $$$A_i$$$ ($$$1 \le i \le N$$$), which is a positive integer between $$$1$$$ and $$$N$$$. No two buildings have the same height.

Initially, both players are to the left of all buildings. At every integer moment $$$i$$$($$$\ge 1$$$), both players fire one shot each at the same time, and the bullets fly horizontally to the right from where they were fired. Both bullets have the same speed. The player selects the bullet's firing height as the distance $$$H$$$ from the ground. The height $$$H$$$ is an integer between $$$1$$$ and $$$N + 1$$$. Both players can choose the same height.

If a player's bullet firing height is $$$H$$$, the leftmost building that satisfies $$$A_i \ge H$$$ and has not yet been destroyed will be destroyed by this bullet. If no building satisfies this condition, nothing happens. If both players hit the same building, only that one building is destroyed. For example, if $$$A_1 = 2$$$, $$$A_2 = 1$$$, and both players initially set $$$H = 1$$$ as the firing height, building 1 will be destroyed, but building 2 will stay in place.

Given the heights of $$$N$$$ buildings, find the minimum time to destroy all the buildings, and provide any sequence of firing heights that achieves this.

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 100\,000$$$).

The next line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le N$$$, all $$$A_i$$$ are distinct).

On the first line, output a single integer $$$T$$$ denoting the minimum time.

On each of the next $$$T$$$ lines, output two integers denoting the firing heights of the two players. Both integers should be at least $$$1$$$, and at most $$$N+1$$$. The two integers can be equal.

8
4 3 8 2 1 7 6 5

4
4 8
3 7
2 6
1 5

8
5 6 7 1 2 8 3 4

4
5 6
7 8
1 2
3 4

4
1 2 4 3

2
4 1
2 3