24729번 - 심각한 계단 중독입니다

병철이는 다이어트를 위해 매일 계단을 오른다. 너무 많은 계단을 오르다 보니, 주변의 모든 사물이 계단형이 아니면 불편함을 느끼게 되었다!

그러다 보니 알고리즘 문제를 풀 때도 이런 문제나 저런 문제가 아니면 불편함을 느끼게 되었고, 이 심각한 계단 중독이 점점 악화되어가자 아예 입력 데이터가 계단이 아니면 불편함을 느끼게 되었다!

결국, 병철이는 백준을 해킹하여 모든 데이터를 계단 수로 만들려고 결심하였다.

여기서 계단 수란, 어떤 수의 앞과 뒤에 있는 수가 그 수와 $1$ 차이가 나는 수열을 말한다. 즉, $1-2-3-4-5$ 같은 수열이나 $1-2-3-2-3$ 같은 수열을 계단 수라고 한다.

하지만 병철이는 여기서 만족하지 않고, 기존 계단 수에 조건을 추가해 본인만의 계단 수를 정의하려고 한다.

병철이의 계단 수란, 기존에 계단 수의 조건을 만족하며 맨 앞의 수와 맨 뒤의 수까지 $1$ 차이가 나는 것을 말한다. 즉, $1-2-3-2-3-2$ 같은 수열이 병철이의 계단 수라고 할 수 있다.

물론 순서를 조정해서 병철이의 계단 수를 만들 수 있는 문제는 얼마 없기 때문에, 병철이는 이 조건을 만족하는 데이터만 찾으려고 한다. 어떤 데이터가 주어질 때, 이 데이터의 순서를 조정하여 병철이의 계단 수를 만들 수 있는지 알아보자.

첫 줄에는 데이터의 크기 $N$이 주어진다. $(1 \leq N \leq 50\,000)$

두 번째 줄에는 데이터에 포함된 값인 $a_0, a_1, \cdots a_{N-1}$이 주어진다. $(1 \leq a_i \leq 100\,000)$

병철이의 계단 수를 만들 수 있다면 1을, 없다면 -1을 출력한다.