Rigging the Draw

For the school festival, Kusagwa built a game that charges an entry fee and lets many people play at once. The heart of the game is a draw machine. The machine has positions $1$ through $N$ arranged in a circle, and every position has one hole on top and one hole underneath. A marble dropped into a top hole travels through fixed passages inside and falls out of one of the bottom holes.

The rules are simple. $N$ people gather and one person stands at each position from $1$ to $N$. Kusagwa drops one marble into the top hole of person $1$, then person $2$, and so on through person $N$, and watches where each marble comes out. If a marble comes out of the bottom hole of the same position, nothing happens. If it comes out anywhere else, that person wins a prize. There is one catch: if every marble comes out at a position other than its own, the round is a jackpot and nobody wins a prize.

People who know nothing about the inside of the machine think the prizes come easily, but Kusagwa did the arithmetic. The marbles look random, and in fact each one lands exactly where the passages send it.

Building the first machine was very hard, copying it is easy. Attaching identical copies underneath gives what looks like one larger machine with a longer, flashier path, while the outcome stays exactly what Kusagwa chose. In a stack of $k$ machines, a marble dropped at position $i$ moves to position $J_i$ in the first machine, to position $J_{J_i}$ in the second, and falls out at the position reached after $k$ such moves.

For example, the machine $J = (2, 1, 4, 3)$ already pays off for Kusagwa on its own. Stacking two copies sends every marble back to its own position and nothing happens, and stacking three copies again sends every marble somewhere else.

Kusagwa wants to stack at least two machines to make the game tense. Person $1$, then person $2$, and so on watch their marbles come out somewhere else and get excited, and the moment person $N$'s marble also lands elsewhere, Kusagwa plans to announce that it really did happen. Given one machine, find how many copies Kusagwa has to stack to come out ahead.

The first line contains an integer $N$ ($1 \le N \le 10^6$).

The second line contains $N$ integers $J_1, J_2, \dots, J_N$ separated by spaces ($1 \le J_i \le N$). $J_i$ is the position where a marble dropped at position $i$ lands after passing through one machine. The $J_i$ are not guaranteed to be distinct.

Print the smallest $k$ that makes every person's marble land at a position other than their own. $k$ must satisfy $2 \le k \le 2 \times 10^9$. If no such $k$ exists in that range, print -1.