Artsem has a friend Saunders from University of Chicago. Saunders presented him with the following problem.

Let [*n*] denote the set {1, ..., *n*}. We will also write *f*: [*x*] → [*y*] when a function *f* is defined in integer points 1, ..., *x*, and all its values are integers from 1 to *y*.

Now then, you are given a function *f*: [*n*] → [*n*]. Your task is to find a positive integer *m*, and two functions *g*: [*n*] → [*m*], *h*: [*m*] → [*n*], such that *g*(*h*(*x*)) = *x* for all <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/a256711cc012560db991a322ff7b75323883dd8e.png" style="max-width: 100.0%;max-height: 100.0%;"/>, and *h*(*g*(*x*)) = *f*(*x*) for all <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2ad9b8e566fe6c09697f5cee64720999d04e8a6f.png" style="max-width: 100.0%;max-height: 100.0%;"/>, or determine that finding these is impossible.
The first line contains an integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>).

The second line contains *n* space-separated integers — values *f*(1), ..., *f*(*n*) (1 ≤ *f*(*i*) ≤ *n*).
none
3
1 2 3
3
1 2 3
1 2 3
3
2 2 2
1
1 1 1
2
2
2 1
-1
1
1
1
1
1
2
2 1
-1
2
2 2
1
1 1
2
5
5 5 5 3 5
-1
10
4 4 4 4 4 4 4 4 4 4
1
1 1 1 1 1 1 1 1 1 1
4
2
1 2
2
1 2
1 2
3
3 2 3
2
2 1 2
2 3
3
1 2 1
2
1 2 1
1 2
4
4 2 4 4
2
2 1 2 2
2 4
5
1 4 5 4 5
3
1 2 3 2 3
1 4 5
4
1 2 1 2
2
1 2 1 2
1 2
5
1 3 3 4 4
3
1 2 2 3 3
1 3 4
4
4 2 2 4
2
2 1 1 2
2 4
7
7 3 3 5 5 7 7
3
3 1 1 2 2 3 3
3 5 7
6
1 1 1 3 3 3
-1
4
2 2 3 2
2
1 1 2 1
2 3
6
1 2 3 4 5 5
5
1 2 3 4 5 5
1 2 3 4 5
3
1 1 2
-1
4
3 4 3 4
2
1 2 1 2
3 4
6
1 1 1 4 4 4
2
1 1 1 2 2 2
1 4
4
1 2 1 1
2
1 2 1 1
1 2
5
1 2 3 4 3
4
1 2 3 4 3
1 2 3 4
4
2 2 4 4
2
1 1 2 2
2 4
4
1 1 3 3
2
1 1 2 2
1 3
3
2 2 3
2
1 1 2
2 3
5
5 3 3 3 5
2
2 1 1 1 2
3 5
n = int(input())
f = list(map(int, input().split()))
h = list(set(f))
if any(f[i - 1] != i for i in h):
    print(-1)
    exit()
d = [0] * n
for i, j in enumerate(h, 1): d[j - 1] = i
g = [d[f[i] - 1] for i in range(n)]
print(len(h), ' '.join(map(str, g + h)))