Shortest Cycle

Description:

Input:

The first line contains one integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — number of numbers.

The second line contains $$$n$$$ integer numbers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{18}$$$).

Output:

If the graph doesn't have any cycles, output $$$-1$$$. Else output the length of the shortest cycle.

Sample Input:

4
3 6 28 9

Sample Output:

4

Sample Input:

5
5 12 9 16 48

Sample Output:

3

Sample Input:

4
1 2 4 8

Sample Output:

-1

Note:

In the first example, the shortest cycle is $$$(9, 3, 6, 28)$$$.

In the second example, the shortest cycle is $$$(5, 12, 9)$$$.

The graph has no cycles in the third example.