#739 Three-Dimensional Ladder Game

Statement

Statement language

There are $N$ vertical poles, one at each vertex of a regular $N$ -gon. Viewed from above, the poles are numbered $1,2,\cdots,N$ in clockwise order.

You may add horizontal rungs at arbitrary heights, each joining two adjacent poles. Poles $1$ and $N$ are also adjacent. Multiple rungs may join the same pair of poles, and distinct rungs may be placed at the same height. However, two rungs at the same height must not share an endpoint pole.

Starting at the top of a pole, move downward. Whenever you encounter a rung, follow it to the other pole and continue downward. Repeat until you reach the bottom.

You are given a permutation $A_1,A_2,\cdots,A_N$ . Arrange the rungs so that starting at the top of pole leads to the bottom of pole .

Find the minimum possible number of rungs.

Input

The input is given in the following format:

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

Output

Print the minimum possible number of rungs on a single line.

Constraints

$3 \leq N \leq 1000$ .
$1 \leq A_i \leq N$ ().

Subtasks

#	Score	Constraints
1	20	$N \leq 5$ .
2	30	$N \leq 50$ .
3	50	No additional constraints.

Samples

Sample 1

Input

3
2 1 3

Output

1

Sample 2

Input

5
1 2 3 4 5

Output

0

Sample 3

Input

5
3 4 5 1 2

Output

6

Sample 4

Input

6
6 5 4 3 2 1

Output

7