주작 주 주작

학교 축제를 앞두고 쿠사과는 참가비를 받고 여러 사람이 동시에 즐기는 게임을 만들었다. 이 게임의 핵심은 추첨기다. 추첨기에는 $1$번부터 $N$번까지 자리가 둥글게 놓여 있고, 자리마다 위와 아래에 구멍이 하나씩 있다. 위쪽 구멍에 구슬을 넣으면 구슬은 안에서 정해진 통로를 따라 복잡하게 움직인 뒤 아래쪽 구멍 중 하나로 떨어진다.

게임 방식은 간단하다. $N$명이 모여 $1$번부터 $N$번 자리에 한 명씩 선다. 쿠사과는 $1$번 사람부터 $N$번 사람까지 차례로 그 사람 자리의 위쪽 구멍에 구슬을 하나씩 넣고, 구슬이 어디로 떨어지는지 확인한다. 구슬이 자기 자리의 아래쪽 구멍으로 그대로 나오면 아무 일도 없지만, 다른 자리로 떨어지면 그 사람은 경품을 받는다. 단 모든 사람의 구슬이 자기 자리가 아닌 곳으로 떨어지면 그 판은 잭팟이 되어 아무도 경품을 받지 못한다.

추첨기 안을 모르는 사람은 경품을 받기 쉬운 게임이라고 생각하지만, 쿠사과의 계산은 달랐다. 구슬이 무작위로 떨어지는 것처럼 보여도 실제로는 통로가 정해 둔 자리로 떨어질 뿐이다.

추첨기를 처음 하나 만드는 일은 아주 어려웠지만 복제하는 일은 쉬웠다. 그래서 같은 추첨기를 아래에 계속 이어 붙이면 겉으로는 한 대의 큰 추첨기처럼 보이고 구슬은 더 화려하게 움직이지만, 결과는 여전히 쿠사과가 정한 대로 나온다. 추첨기 $k$대를 이어 붙인 기계에서는 $i$번 자리에 넣은 구슬이 첫 번째 추첨기에서 $J_i$번으로, 두 번째 추첨기에서 $J_{J_i}$번으로 옮겨 가며, $k$번 옮긴 자리에서 떨어진다.

예를 들어 $J = (2, 1, 4, 3)$인 추첨기는 그것만으로 이미 쿠사과에게 이득이다. 이 추첨기를 두 대 이어 붙이면 모든 구슬이 제자리로 돌아와 아무 일도 일어나지 않지만, 세 대를 이어 붙이면 다시 모든 구슬이 다른 자리로 떨어진다.

쿠사과는 게임의 박진감을 살리려고 추첨기를 두 대 이상 이어 붙일 생각이다. $1$번 사람부터 차례로 다른 자리에서 구슬이 나와 모두가 신나다가 $N$번 사람의 구슬까지 다른 자리로 떨어지는 순간, 쿠사과는 "아이쿠 그런데 그것이 실제로 일어났습니다"라고 말할 참이다. 추첨기가 주어질 때, 쿠사과가 이득을 보려면 추첨기를 몇 대 이어 붙여야 하는지 구하라.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 10^6$)

둘째 줄에 정수 $J_1, J_2, \dots, J_N$이 공백으로 구분되어 주어진다. ($1 \le J_i \le N$) $J_i$는 $i$번 자리에 넣은 구슬이 추첨기 한 대를 지나 떨어지는 자리다. $J_i$가 서로 다르다는 보장은 없다.

모든 사람의 구슬이 자기 자리가 아닌 곳으로 떨어지게 만드는 가장 작은 $k$를 출력한다. $k$는 $2 \le k \le 2 \times 10^9$을 만족해야 하며, 이 범위에 그런 $k$가 없으면 -1을 출력한다.