A10843 | Artsem and Saunders

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 , and $h(g(x))=f(x)$ for all , or determine that finding these is impossible.

The first line contains an integer $n$ ( $1<=n<=10^{5}$ ).

The second line contains $n$ space-separated integers — values $f(1),...,f(n)$ ( $1<=f(i)<=n$ ).

If there is no answer, print one integer -1.

Otherwise, on the first line print the number $m$ ( $1<=m<=10^{6}$ ). On the second line print $n$ numbers $g(1),...,g(n)$ . On the third line print $m$ numbers $h(1),...,h(m)$ .

If there are several correct answers, you may output any of them. It is guaranteed that if a valid answer exists, then there is an answer satisfying the above restrictions.