Block Game

$N$ blocks stand in a row. The leftmost block is block 1, the block to its right is block 2, and in the same way the rightmost block is block $N$. Block $i$ has height $H_i$.

One small machine sits in front of the row. At the start it is in front of block 1. The goal is to remove all of the blocks with that machine. The heights written down in removal order must form a non-decreasing sequence.

The machine takes three commands.

• Move to the block on the right. If the machine was in front of block $i$, it goes in front of block $i+1$. You cannot give this command when there is no block on the right.
• Move to the block on the left. If the machine was in front of block $i$, it goes in front of block $i-1$. You cannot give this command when there is no block on the left.
• Remove the block in front of the machine and move to the block on the left or on the right. You fix the direction when you give the command. If no block is left on either side after the removal, the machine does not have to move.

Removing a block renumbers the remaining blocks. Suppose the heights from the left are $(2, 3, 4, 5, 6)$ and the machine is in front of the block of height 4. That block is third from the left, so it is block 3. Remove it and move left: the heights become $(2, 3, 5, 6)$ and the machine is in front of the block of height 3, which is block 2. Move right instead: the heights are the same $(2, 3, 5, 6)$ and the machine is in front of the block of height 5, which is block 3.

Write a program that computes the minimum number of commands needed to reach the goal.

A sequence $A_1, A_2, \dots, A_K$ of length $K$ is non-decreasing when it satisfies $A_1 \le A_2 \le \dots \le A_K$.

The first line contains the number of blocks $N$. ($1 \le N \le 100000$)

The second line contains the heights $H_1, H_2, \dots, H_N$ in order. ($1 \le H_i \le 100000$)

Print the minimum number of commands needed to reach the goal on the first line.

The first example is solved with the commands below. The block in front of the machine is shown in square brackets.

• Start: [1] 2 3
• Remove and move right: [2] 3
• Remove and move right: [3]
• Remove

The second example needs these commands.

• Start: [4] 2 1 3
• Move right: 4 [2] 1 3
• Move right: 4 2 [1] 3
• Remove and move left: 4 [2] 3
• Remove and move right: 4 [3]
• Remove and move left: [4]
• Remove