Candies

$N$명의 아이가 한 줄로 서 있다. 아이들에게는 $1,2,\cdots,N$의 번호가 하나씩 붙어 있다. 처음에는 왼쪽부터 $P_1,P_2,\cdots,P_N$번 아이가 서 있으며, 모든 아이가 가진 사탕의 개수는 $0$이다.

한 번의 조작으로, 현재 줄에서 연속한 $3$명의 아이를 고른다. 세 아이가 왼쪽부터 각각 $a,b,c$번 아이라고 하자. 아이들은 자신이 가진 사탕의 개수에 매우 민감하므로, 세 아이가 가진 사탕의 개수가 모두 같을 때만 조작할 수 있다. 조작을 하면 세 아이에게 사탕을 하나씩 주고, 순서를 $a,b,c$에서 $b,c,a$로 바꾼다.

아이들을 왼쪽부터 $1,2,\cdots,N$번 순서로 정렬하기 위해 필요한 조작 횟수의 최솟값을 구하여라. 불가능하다면 $-1$을 출력한다.

입력은 다음과 같은 형식으로 주어진다.

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

정답을 출력한다.

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