# KOI 22 Parking Tower

https://www.acmicpc.net/problem/25404

There is a circular parking tower with $N$ spaces arranged in a circle. Each space is called the $1$-st, $2$-nd, $\dots$, $N$-th space in clockwise order. Each space contains one car, and the car in the $i$-th space has the number $a_i$.


The parking tower has two buttons. Pressing button A rotates the parking tower one space clockwise, and pressing button B rotates the parking tower one space counterclockwise. The left picture below shows the state after pressing button A, and the right picture shows the state after pressing button B in the given example.


We want to remove all cars from the parking tower.

Cars can only be removed from the single space at the bottom. Initially, the $1$-st space is at the bottom. To remove a car from a space that is not at the bottom, you must first press the buttons appropriately to rotate the parking tower so that the space with the car is moved to the bottom.

Additionally, to remove the car with number $x$, you must first remove all cars with numbers less than $x$. In other words, if there are cars with numbers less than $x$ remaining in the parking tower, the car with number $x$ cannot be removed.

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

## Input

The first line contains an integer $N$.

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

## Output

Print the minimum number of button presses required.

## Constraints
* $1≤N≤100,000$
* $1≤a_i≤1,000,000,000$

## Subtasks

1. 8 points: $a_i = 1$ for all $1 \leq i \leq N$, i.e., all car numbers are $1$.
1. 9 points: $a_i \neq a_j$ for $i \neq j$, i.e., all car numbers are different.
1. 10 points: $N \leq 10$.
1. 21 points: $N \leq 100$.
1. 31 points: $N \leq 1,000$.
1. 21 points: No additional constraints.

## Examples

### Sample Input 1

4
1 2 2 1

### Sample Output 1

`3`

Remove car $\rightarrow$ Press button A $\rightarrow$ Remove car $\rightarrow$ Press button A $\rightarrow$ Remove car $\rightarrow$ Press button A $\rightarrow$ Remove car.

### Sample Input 2

5
3 1 4 5 1

### Sample Output 2

`7`