총 쏘기

두 명이 같이 하는 인터넷 슈팅 게임이 있다. 이 게임은 폐허가 된 도시에서 빌딩들을 부수는 게임이다. 게임에서 바닥인 수평선 위에 $N$개의 빌딩이 왼쪽에서 오른쪽으로 서 있다. 빌딩은 왼쪽에서 오른쪽으로 순서대로 1부터 $N$의 정수로 나타낸다. 각 빌딩의 바닥으로부터의 높이는 수열 $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$만 파괴된다. 

문제는 $N$개 빌딩들의 높이가 입력으로 주어질 때, 모든 빌딩을 파괴할 수 있는 최소 시간과 각 시간에 두 플레이어의 총알 발사 높이를 찾는 것이다.

첫째 줄에 정수 $N$이 주어진다.

다음 줄에는 $N$개의 공백으로 구분된 정수 $A\_1, A\_2, \ldots, A\_N$이 주어진다.

첫째 줄에 두 플레이어가 모든 빌딩을 파괴하기 위한 최소 시간 $T$를 출력한다.

다음 $T$개의 줄에는 공백으로 구분된 두 정수를 한 줄에 하나씩 출력한다. 두 정수는 각각 첫 번째와 두 번째 플레이어의 총알 발사 높이를 나타낸다. 두 정수는 1보다 크거나 같고, $N+1$보다 작거나 같아야 하며, 두 정수가 서로 같아도 된다.

• $1 \le N \le 100\\,000$
• $1 \le A\_i \le N$ $(1 \le i \le N)$
• $A\_i$ $(1 \le i \le N)$는 모두 서로 다르다.