완벽한 합창단

합창단 지휘자가 브라질 합창 주간 공연에 올릴 새 곡을 구상했다. 곡의 규칙은 다음과 같다.

• 각 단원은 처음에 정해진 음 하나를 부르기 시작하고, 지휘자가 지시할 때만 음을 바꾼다.
• 매 마디가 끝날 때 지휘자는 정확히 두 단원에게 음을 바꾸라고 지시한다. 한 단원은 자신이 부르던 음의 바로 위 음을 부르고, 다른 단원은 바로 아래 음을 부른다.
• 모든 단원이 같은 음을 부르는 첫 마디가 끝나면 곡이 끝난다.

곡의 마디 수는 곡이 끝날 때까지 지난 마디의 개수다. 처음부터 모든 단원이 같은 음을 부르면 첫 마디가 끝날 때 곡이 끝나므로 마디 수는 1이다.

지휘자는 시작 음을 단원에게 어떻게 나눠 줄지 여러 안을 이미 마련해 두었다. 다만 주어진 배치에서 원하는 방식으로, 즉 모든 단원이 같은 음을 부르는 상태로 곡을 끝낼 수 있는지, 끝낼 수 있다면 마디 수가 최소 몇 개인지 알고 싶다. 지휘자를 도와주자.

입력은 여러 개의 테스트 케이스로 이루어지고, 입력의 끝까지 이어진다.

각 테스트 케이스의 첫 줄에는 합창단 단원 수 $N$이 주어진다. 둘째 줄에는 각 단원이 처음에 부를 음 $N$개가 음높이의 비내림차순으로 주어진다. 음은 정수로 나타내고, 어떤 음의 바로 위 음은 그 값보다 $1$ 큰 정수, 바로 아래 음은 $1$ 작은 정수다.

제약

• $2 \le N \le 10^4$
• $-10^5 \le nota_i \le 10^5$ ($0 \le i \le N - 1$)
• $nota_i \le nota_{i+1}$ ($0 \le i \le N - 2$)

각 테스트 케이스마다 곡의 최소 마디 수를 한 줄에 출력한다. 모든 단원이 같은 음을 부르는 상태로 곡을 끝낼 수 없으면 $-1$을 출력한다.