미친 춤

조커는 광기로 유명하다. 그래서 그는 밑이 $a$인 위치 기수법을 쓰며, 이 기수법에서 모든 수는 $0$부터 $a - 1$까지의 숫자로 이루어진다. 조커는 춤추는 것도 아주 좋아한다. 그는 매우 오래 춤출 수 있어서, 영원히 추지 않도록 스스로 규칙을 정했다. 그 규칙도 이상하다. 춤을 추는 동안 첫 초부터 매초마다 춤을 시작한 뒤 지난 초의 수를 $a$진법으로, 앞에 0을 붙이지 않고 소리 내어 말한다. $a = 3$이면 처음 다섯 수는 1초부터 5초까지 차례로 $1$, $2$, $10$, $11$, $12$이다.

조커는 음이 아닌 정수 $a$개로 이루어진 배열 $b_i$를 골랐다. 그는 말한 수 중 하나를 말한 뒤, 춤을 시작한 뒤로 모든 $0 \le i < a$에 대해 숫자 $i$를 정확히 $b_i$번 말했다면 춤을 멈추기로 했다. 춤이 몇 초 동안 이어지는지 구하라. 영원히 끝나지 않으면 그렇다고 알려라.

첫 줄에 기수 $a$가 주어진다($2 \le a \le 100\,000$). 둘째 줄에 정수 $a$개 $b_i$가 주어진다($0 \le b_i \le 10^9$).

조커의 춤이 영원히 끝나지 않으면 $-1$을 출력한다. 그렇지 않으면 춤이 지속되는 시간을 초 단위로 출력한다.