There is a circular parking tower with $N$ compartments arranged in a circle. They are called compartment 1, compartment 2, ..., compartment $N$ in clockwise order. Each compartment contains one car. The car in compartment $i$ has number $a_i$.

The tower has two buttons. Pressing button A rotates it one compartment clockwise, while pressing button B rotates it one compartment counterclockwise. The left figure below shows the example above after pressing A, and the right figure shows it after pressing B.

We want to remove all cars from the tower.

Cars can only be removed from the single compartment at the very bottom. Initially, compartment 1 is at the bottom. To remove a car from another compartment, first press the buttons appropriately to rotate its compartment to the bottom.

In addition, before removing a car numbered $x$, all cars with numbers smaller than $x$ must have been removed. In other words, if any car with a number less than $x$ remains in the tower, a car numbered $x$ cannot be removed.

Write a program to find the minimum total number of button presses needed to remove all cars from the tower.

Constraints

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

Subtasks

1. (8 points) $a_i=1$ ($1\le i\le N$), that is, all cars have number 1.
2. (9 points) $a_i\ne a_j$ whenever $i\ne j$, that is, all cars have distinct numbers.
3. (10 points) $N\le10$.
4. (21 points) $N\le100$.
5. (31 points) $N\le1\,000$.
6. (21 points) No additional constraints.

Input

The first line contains an integer $N$.

The second line contains the car numbers $a_1,\ldots,a_N$ in order, separated by spaces.

Output

On the first line, output the minimum total number of button presses.

Examples

Input 1

4
1 2 2 1

Output 1

3

Note

Proceed in this order: remove a car → button A → remove a car → button A → remove a car → button A → remove a car.

Input 2

5
3 1 4 5 1

Output 2

7