There is an online shooting game played by two people. The game involves destroying buildings in a ruined city.

In the game, $N$ buildings stand on a horizontal floor from left to right. The buildings are numbered from $1$ to $N$ in order from left to right. The height of each building from the floor is given by a sequence $A_i$ ($1 \le i \le N$), which consists of distinct integers from $1$ to $N$.

Two players are at the same position to the left of all buildings. At time $i$ ($\ge 1$), both players simultaneously fire one shot each, and the bullets travel horizontally to the right from the firing position. The speed of both bullets is the same. Players determine the firing height of their bullets as a distance $H$ from the floor. $H$ is an integer between $1$ and $N+1$, inclusive. The two players can choose the same firing height.

If a player's bullet firing height is $H$, the leftmost undestroyed building that satisfies $A_i \ge H$ is destroyed by this bullet. If no building satisfies this condition, nothing happens. If the buildings satisfying this condition for the bullets fired by the two players are the same, only this one building is destroyed (because the speeds of the two bullets are the same). Specifically, if the two players choose the same firing height, only one building is always destroyed. For example, if $A_1 = 2, A_2 = 1$ and both players initially decide on a firing height of $H = 1$, only building 1 is destroyed by these two bullets.

The problem is to find the minimum time required to destroy all buildings and the firing heights of the two players at each time, given the heights of the $N$ buildings as input.

Implementation Details

You must implement the following function:

vector< pair<int, int> > min_shooting_buildings(vector<int> A)

• This function is called exactly once.
• The size of the given array $A$ is $N$. Each element $A[i]$ of the array represents the height $A_{i+1}$ of building $i+1$ ($0 \le i \le N - 1$).
• This function returns an array $M$ of size $S$, where $S$ is the minimum time required for the two players to destroy all buildings. Each element $(a, b)$ of array $M$ represents the firing heights of the first and second player, respectively.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le N \le 100\,000$
• $1 \le A_i \le N$ ($1 \le i \le N$)
• $A_i$ ($1 \le i \le N$) are all distinct.

Subtasks

1. (17 points) There does not exist $(i, j, k)$ such that $1 \le i < j < k \le N$ and $A_i < A_j < A_k$.
2. (12 points) There does not exist $(i, j, k)$ such that $1 \le i < j < k \le N$ and $A_i > A_j > A_k$.
3. (9 points) $N \le 4$
4. (12 points) $N \le 16$
5. (31 points) $N \le 500$
6. (29 points) $N \le 7\,500$
7. (40 points) No additional constraints.

Scoring

The data is considered correct if the size of the array returned by the min_shooting_buildings function is equal to the minimum time $S$ required for the two players to destroy all buildings, and all buildings are destroyed when the two players fire their shots as specified by the elements of the returned array.

Examples

• Consider the case where $N = 4$ and $A = [1, 2, 4, 3]$. The grader calls the following function:

  min_shooting_buildings([1, 2, 4, 3])

  As shown in Figure 1 below, if the firing positions of the two players are determined as $(1, 2), (3, 4), (3, 3)$, all buildings are destroyed in 3 units of time.

  

  Figure 1

  As shown in Figure 2 below, if the firing positions of the two players are determined as $(1, 4), (2, 3)$, all buildings are destroyed in 2 units of time.

  

  Figure 2

  The min_shooting_buildings function must return an array of size 2, and one of the possible contents of the array is [(1, 4), (2, 3)].

• Consider the case where $N = 8$ and $A = [4, 3, 8, 2, 1, 7, 6, 5]$. The min_shooting_buildings function must return an array of size 4, and one of the possible contents of the array is [(4, 8), (3, 7), (2, 6), (1, 5)].

• Consider the case where $N = 8$ and $A = [5, 6, 7, 1, 2, 8, 3, 4]$. The min_shooting_buildings function must return an array of size 4, and one of the possible contents of the array is [(5, 6), (7, 8), (1, 2), (3, 4)].

Sample grader

The sample grader receives input in the following format:

• Line 1: $N$
• Line 2: $A[0] \ A[1] \ \dots \ A[N - 1]$

The sample grader outputs the following:

• Line $i$ ($1 \le i \le S$): The $i$-th element of the array returned by the function min_shooting_buildings.

Note that the sample grader may differ from the grader used in actual evaluation.