Problem Statement

There are $10^{100}$ squares arranged in a row. The $i$-th square from the left ($1 \leq i \leq 10^{100}$) is called square $i$.
There are also $N$ pieces, and the $i$-th piece ($1 \leq i \leq N$) is initially placed on square $A_i$.
Find the minimum number of operations required to reach a state where squares $1,2,\dots,N$ each have $1$ piece on them, by repeating the following operation.

• Choose $1$ piece, and let $x$ be the square it is on. Perform one of the following $2$ moves.
  • Move the chosen piece to the rightmost square without a piece among squares $1,2, \dots, x-1$. However, this move cannot be performed if all of the squares $1, 2, \dots, x-1$ have pieces on them.
  • Move the chosen piece to the leftmost square without a piece among squares $x+1, x+2, \dots, 10^{100}$. However, this move cannot be performed if all of the squares $x+1, x+2, \dots, 10^{100}$ have pieces on them.

Input

The input is given from standard input in the following format.

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print the answer to standard output in $1$ line. Add a newline at the end.

Constraints

The input satisfies the following constraints.

• $1 \leq N \leq 100\,000$
• $1 \leq A_1 \lt A_2 \lt \cdots A_N \leq 10^9$
• All input values are integers.

Sample

3
2 4 5

2

1
1000000000

999999999