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

Input

The first line contains an integer n (1 ≤ n ≤ 105).

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 ≤ 106). 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

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

//change to Main!
//chhange to TestClass
public class Main {

	static class Pair implements Comparable<Pair> {

		int x;
		int y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(Pair o) {
			int comp1 = Integer.compare(x, o.x);
			if (comp1 != 0) {
				return comp1;
			}
			return Integer.compare(y, o.y);
		}

		@Override
		public String toString() {
			return "(" + x + ", " + y + ")";
		}

	}

	static int MOD = 1000 * 1000 * 1000 + 7;
	private static InputReader in;
	private static PrintWriter out;

	public static void shuffleArray(int[] arr) {
		int n = arr.length;
		Random rnd = new Random();
		for (int i = 0; i < n; ++i) {
			int tmp = arr[i];
			int randomPos = i + rnd.nextInt(n - i);
			arr[i] = arr[randomPos];
			arr[randomPos] = tmp;
		}
	}

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		in = new InputReader(inputStream);
		out = new PrintWriter(outputStream);
		solve();
		out.close();
		System.exit(0);
	}

	static int[] comp;
	static int[] big;

	private static void solve() {

		int n = in.nextInt();
		int[] f = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			f[i] = in.nextInt();
		}

		Pair[] tab = new Pair[n];
		for (int i = 1; i <= n; i++) {
			Pair p = new Pair(f[i], i);
			tab[i - 1] = p;
		}

		Arrays.sort(tab);
		comp = new int[n + 1];
		big = new int[n + 1];
		int res = 1;
		for (int i = 0; i < n;) {
			Pair curr = tab[i];
			while (i < n && curr.x == tab[i].x) {
				comp[tab[i].y] = res;
				big[tab[i].x] = res;
				i = i + 1;
			}
			res++;
		}

		// max f value = res

		// check if possible

		boolean isOk = true;
		for (int i = 1; i <= n; i++) {
			int value = f[i];
			int desiredComp = big[value];
			if (comp[value] != desiredComp) {
				isOk = false;
			}
		}

		if (!isOk) {
			out.println(-1);
			return;
		}

		res -= 1;
		int[] h = new int[res + 1];
		int pos = 1;
		for (int i = 0; i < tab.length;) {
			h[pos] = tab[i].x;
			while (i < n && h[pos] == tab[i].x) {
				i++;
			}
			pos++;
		}

		int g[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			int val = f[i];
			g[i] = big[val];
		}

		out.println(res);
		for (int i = 1; i <= n; i++) {
			out.print(g[i] + " ");
			if (i == n) {
				out.println();
			}
		}
		for (int i = 1; i <= res; i++) {
			out.print(h[i] + " ");
		}

	}

	public static void swap(int[] tab, int i, int j) {
		int tmp = tab[i];
		tab[i] = tab[j];
		tab[j] = tmp;
	}

	/*
	 * 
	* 
	*/
	// --------------------------------------------------------

	static int gcd(int n, int m) {
		if (m == 0) {
			return n;
		}

		return gcd(m, n % m);
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String nextLine() {
			String str = "";
			try {
				str = reader.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}

			return str;
		}
	}

}