#491 Candies

Loading problem...

Preparing the statement, recent submissions, and submit form.

#491 Candies

Authors: pk661

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

There are $N$ children standing in a line, numbered $1,2,\cdots,N$ . Initially, the children from left to right are $P_1,P_2,\cdots,P_N$ , and every child has $0$ candies.

In one operation, choose three consecutive children. Let their numbers from left to right be $a,b,c$ . The children are very sensitive to how many candies they have, so the operation can be performed only if all three children have the same number of candies. Give one candy to each of them, then change their order from $a,b,c$ to $b,c,a$ .

Find the minimum number of operations required to sort the children into the order $1,2,\cdots,N$ from left to right. If it is impossible, print $-1$ .

Input

The input is given from Standard Input in the following format:

$N$ $P_1\ P_2\ \cdots\ P_N$

Output

Output the answer.

Constraints

$1 \le N \le 200\,000$ .
$1 \le P_i \le N$ ().

Subtasks

#	Score	Constraints
1	31	$N \le 3000$ .
2	30	It is guaranteed that the children can be sorted into the order $1,2,\cdots,N$ .
3	39	No additional constraints.

Samples

Sample 1

Input

6
4 1 3 6 2 5

Output

Sample 2

Input

3
2 1 3

Output

-1

Sample 3

Input

1
1

Output

Editorial

View editorial