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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Locale;
import java.util.PriorityQueue;



public final class CF_397_Artsem{

	static void log(int[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}


	static void log(long[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}
	static void log(Object[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}


	static void log(Object o){
		logWln(o+"\n");
	}

	static void logWln(Object o){
		System.err.print(o);
		//outputWln(o);

	}
	static void info(Object o){
		System.err.println(o);
		//output(o);
	}

	static void output(Object o){

		outputWln(""+o+"\n");

	}

	static void outputWln(Object o){
		// System.out.print(o);

		try {
			out.write(""+ o);
		} catch (Exception e) {

		}
	}








	// Global vars
	static BufferedWriter out;

	static void process() throws Exception {


		Locale.setDefault(Locale.US);

		out = new BufferedWriter(new OutputStreamWriter(System.out));
		InputReader reader=new InputReader(System.in);

	int n=reader.readInt();
	int[] f=new int[n];
	ArrayList<Integer> id=new ArrayList<Integer>();
	HashSet<Integer> img=new HashSet<Integer>();
	int[] inv=new int[n];
	Arrays.fill(inv,-1);
	for (int i=0;i<n;i++){
		f[i]=reader.readInt()-1;
		if (f[i]==i){
			id.add(i);
		}
		inv[f[i]]=i;
		img.add(f[i]);
	}
		
	if (id.size()==0 || img.size()!=id.size()){
		output("-1");
	} else {
		ArrayList<Integer> list=new ArrayList<Integer>();
		list.addAll(id);
		int m=id.size();
		int[] idx=new int[n];
		Arrays.fill(idx,-1);
		for (int i=0;i<m;i++){
			int x=list.get(i);
			idx[x]=i;
		}
		output(m);
		for (int i=0;i<n;i++){
			outputWln((idx[f[i]]+1)+" ");
		}
		output("");
		for (int i=0;i<m;i++){
			outputWln((list.get(i)+1)+" ");
		}
		output("");
	}
	
		try {
			out.close();
		}
		catch (Exception e){}


	}



	public static void main(String[] args) throws Exception {
		process();


	}
	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}


		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res=new StringBuilder();
			do {
				res.append((char)c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			if (d=='-') {
				neg=true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			if (d=='-') {
				neg=true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			if (neg)
				return -res;
			return res;

		}




		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}