$\operatorname{mex}(S)$를 집합 $S$에 포함되지 않은 가장 작은 음이 아닌 정수로 정의합시다.
하치쿠지 마요이(Mayoi Hachikuji)는 $n$개의 원소로 이루어진 배열 $a$를 가지고 있으며, 이 배열이 비내림차순으로 정렬되기를 원합니다. 이를 위해 그녀는 다음 연산을 원하는 만큼(0번 가능) 수행할 수 있습니다:
- 정수 $i \in [1, \operatorname{length}(a) - 2]$를 선택하고, $a_i, a_{i+1}, a_{i+2}$를 그들의 $\operatorname{mex}$로 대체합니다. 이 연산을 적용한 후에는 배열의 길이가 $2$만큼 줄어든다는 점에 유의하십시오.
배열을 비내림차순으로 정렬된 상태로 만들기 위해 마요이가 수행해야 하는 최소 연산 횟수를 구하십시오. 불가능한 경우 $-1$을 출력합니다.
입력
입력의 첫 번째 줄에는 배열 $a$의 길이를 나타내는 정수 $n$ ($2 \le n \le 5 \cdot 10^5$)이 주어집니다.
다음 줄에는 배열 $a$의 원소를 나타내는 $n$개의 정수 $a_i$ ($0 \le a_i \le 10^9$)가 주어집니다.
출력
문제의 답을 나타내는 수 하나를 출력합니다.
예제
예제 입력 1
3 4 1 3
예제 출력 1
1
예제 입력 2
9 3 0 2 2 3 0 4 7 8
예제 출력 2
2
예제 입력 3
2 4 3
예제 출력 3
-1