Block Game

Interview

Time limit2sMemory limit512 MB

Summary

Remove every block so the heights leave in non-decreasing order, minimizing moves of a machine that walks left and right along the shrinking row.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Intervals, Implementation
Solved: No attempts yet

Problem

$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$ .

Input

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$ )

Output

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

Hint

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

Examples5

Example 1
Input
```
3
1 2 3
```
Expected output
```
3
```
Example 2
Input
```
4
4 2 1 3
```
Expected output
```
6
```
Example 3
Input
```
5
5 5 1 5 5
```
Expected output
```
7
```
Example 4
Input
```
10
10 8 6 4 2 1 3 5 7 9
```
Expected output
```
15
```
Example 5
Input
```
10
1 3 5 7 9 10 8 6 4 2
```
Expected output
```
46
```