human
As you have noticed, there are lovely girls in Arpa’s land.

People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi.


Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.

The game consists of rounds. Assume person x wants to start a round, he calls crushx and says: "Oww...wwf" (the letter w is repeated t times) and cuts off the phone immediately. If t > 1 then crushx calls crushcrushx and says: "Oww...wwf" (the letter w is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called the Joon-Joon of the round. There can't be two rounds at the same time.

Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible.

Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crushi = i).

Input

The first line of input contains integer n (1 ≤ n ≤ 100) — the number of people in Arpa's land.

The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.

Output

If there is no t satisfying the condition, print -1. Otherwise print such smallest t.

Examples

Input

4
2 3 1 4

Output

3

Input

4
4 4 4 4

Output

-1

Input

4
2 1 4 3

Output

1

Note

In the first sample suppose t = 3. 

If the first person starts some round:

The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1.

The process is similar for the second and the third person.

If the fourth...
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python code to find such t for Mehrdad if it's possible.

from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
# setrecursionlimit(int(1e6))
inf = float('inf')
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt
def geti(): return map(int, input().strip().split())
def getl(): return list(map(int, input().strip().split()))
def getis(): return map(str, input().strip().split())
def getls(): return list(map(str, input().strip().split()))
def gets(): return input().strip()
def geta(): return int(input())
def print_s(s): stdout.write(s+'\n')

def solve():
    n = geta()
    a = getl()
    edges = dd(list)
    for i in range(n):
        edges[i].append(a[i]-1)
    dist = [[inf]*n for _ in range(n)]
    def dfs(root, par, temp = 0):
        vis[root] = True
        for node in edges[root]:
            dist[par][node] = temp + 1
            if node not in vis:
                dfs(node, par, temp+1)
    ans = []
    vis = dd(int)
    ok = dd(int)
    def dfs(root, par, dist = 0):
        if root == par and dist:
            ok[par] = True
            if dist&1:
                ans.append(dist)
            else:
                ans.append(dist//2)
            return
        if root in vis:
            return
        vis[root] = True
        for node in edges[root]:
            dfs(node, par, dist+1)
    need = []
    for i in range(n):
        if i not in vis:
            need.append(i)
            dfs(i, i)
    # print(ans)
    for i in need:
        if i not in ok:
            print(-1)
            break
    else:
        ans = Counter(ans)
        ans = sorted(ans)
        # print(ans)
        vis = [False]*(len(ans)+1)
        ok = []
        for i in range(len(ans)):
            if ans[i] == 1 or vis[i]:
                continue
            temp = []
            for j in range(i, len(ans)):
                if ans[j] % ans[i] == 0:
                    temp.append(ans[j])
                    vis[j] = True
            now = temp[0]
            g = temp[0]
      ...