Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Artsem and Saunders

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputArtsem 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.

Examples

Input

3

1 2 3

Output

3

1 2 3

1 2 3

Input

3

2 2 2

Output

1

1 1 1

2

Input

2

2 1

Output

-1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 17:38:24 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|