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.

Input

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*$).

Output

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.