시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1024 MB 3 2 2 66.667%

## 문제

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

Initially, both players are to the left of all buildings. At time $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 floor. $H$ is an integer in range $1$ to $N + 1$. Both players can choose the same height.

If the player's bullet firing height is $H$, the leftmost un-destroyed building that satisfies $A_i \ge H$ will be destroyed by this bullet. If no building satisfies this condition, nothing happens. If the building that satisfies this condition for the bullets fired by both players is the same, only this one building is destroyed (since both bullets have the same velocity). In particular, if both players have the same launch height, only one building can be 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 which achieves this.

## 입력

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

The next line contains $N$ space-separated integer $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le N$). All $A_i$'s are distinct.

## 출력

In the first line, print a single integer $T$ denoting the minimum time.

In next $T$ lines, print two space-separated integers denoting the firing heights of both players. Both integers should be at least 1, and at most $N+1$. Both integers can be equal.

## 서브태스크

번호 배점 제한
1 17

There exists no tuple $(i, j, k)$ such that $1 \le i < j < k \le N$ and $A_i < A_j < A_k$ holds.

2 12

There exists no tuple $(i, j, k)$ such that $1 \le i < j < k \le N$ and $A_i > A_j > A_k$ holds.

3 9

$N \le 4$

4 12

$N \le 16$

5 31

$N \le 500$

6 29

$N \le 7\,500$

7 40

4
1 2 4 3

2
1 4
2 3

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

## 채점 및 기타 정보

• 예제는 채점하지 않는다.
• 이 문제의 채점 우선 순위는 2이다.