심각한 계단 중독입니다

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

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

결국 병철이는 해킹으로 모든 데이터를 계단 수로 바꾸기로 결심하였다.

여기서 계단 수란, 어떤 수의 앞과 뒤에 있는 수가 그 수와 $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을 출력한다.