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.OutputStreamWriter;
import java.io.ObjectInputStream.GetField;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
public class first {
	
	static long MOD = 1000000007;
	static boolean b[],bc[];
	static boolean boo[][][];
	static ArrayList<Integer>[] amp,amp1;
	static int sum[],dist[],cnt[];
	static long ans = 0;
	static int p = 0;
	//static ArrayList<Pair3>[][][] pmp;
	static FasterScanner sc = new FasterScanner();
	static Queue<Integer> q = new LinkedList<>();
	static int arr[],start[],color[];
	static PriorityQueue<Integer> pq;
	//static ArrayList<Integer> parent = new ArrayList<>();
	static LinkedList<Integer> fa;
	static BufferedWriter log;
	static TreeMap<Integer,Integer> tm = new TreeMap<>();
	static HashSet<Integer> hs = new HashSet<>();
	static Stack<Integer> stack = new Stack<>();
	static Pair prr[];
	static long parent1[],parent2[],size[][],size1[],size2[];
	public static void main(String[] args) throws Exception {
    	new Thread(null, new Runnable() {
			public void run() {
				try {
					soln();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
    }
	public static void soln() throws IOException {
		log = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = sc.nextInt();
		int arr[] = sc.nextIntArray(n);
		ArrayList<Integer> amp = new ArrayList<>();
		for(int i = 1; i<=n ;i++){
			if(arr[i-1] == i) amp.add(i);
		}
		//System.out.println(amp);
		int h[] = new int[amp.size()+1];
		int g[] = new int[n+1];
		int h1[] = new int[n+1];
		for(int i = 0; i< amp.size();i++){
			h[i+1] = amp.get(i);
			h1[amp.get(i)] = i+1;
		}
		for(int i = 0; i<n;i++){
			if(h1[arr[i]]==0){
				System.out.println(-1);
				return;
			}
			else{
				g[i+1] = h1[arr[i]];
			}
		}
		log.write(amp.size()+"\n");
		for(int i=1;i<=n;i++) log.write(g[i]+" ");
		log.write("\n");
		for(int i=1;i<=amp.size();i++) log.write(h[i]+" ");
		log.write("\n");
		log.close();
	}
	public static void bfs(int x,int arr[]){
	b = new boolean[arr.length];
	b[x] = true;
	q = new LinkedList<>();
	q.add(x);
	while(!q.isEmpty()){
		int y = q.poll();
		for(int i = 0;i<amp[y].size();i++) {
			if(!b[amp[y].get(i)]){
				q.add(amp[y].get(i));
				b[amp[y].get(i)] = true;
				arr[amp[y].get(i)] = (arr[y]+1);
			}
		}
	}
	}
	
	static long get(long x){
		if((x%10)<5) return x-(x%10);
		else return x+(10-x%10);
	}
	static int startTime = 0;
	public static void dfs(int x){
		start[x] = startTime++;
		b[x] = true;
		for(int e:amp[x]){
			if(!b[e]){
				if(x==0){
					color[e] = ++p;
				}
				else color[e] = color[x];
				dfs(e);
				if(x==0) tm.put(color[e], (cnt[e]+1));
				cnt[x] = Math.max(cnt[x],cnt[e]);
			}
		}
		cnt[x]++;
	}
	static long func(long n, long d, long t){
		return (t*(2*(n-1)+(t-1)*(d)))/2;
	}
	static class Pair implements Comparable<Pair> {
		long u;
		long v;
		public Pair(long u, long v) {
			this.u = u;
			this.v = v;
		}
		
		public int hashCode() {
			int hu = (int) (u ^ (u >>> 32));
			int hv = (int) (v ^ (v >>> 32));
			return 31*hu + hv;
		}
 
		public boolean equals(Object o) {
			Pair other = (Pair) o;
			return (u == other.u && v == other.v);
		}
 
		public int compareTo(Pair other) {
			return Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)) : (Long.compare(v, other.v));
		}
		
		public String toString() {
			return "[u=" + u + ", v=" + v + "]";
		}
	}
	public static void buildGraph(int n){
		for(int i =0;i<n;i++){
			int x = sc.nextInt(), y = sc.nextInt();
			amp[--x].add(--y);
			amp[y].add(x);
		}
	}
	
	
	public static long getParent(long x, long parent[]){
		while(parent[(int) x]!=x){
			parent[(int) x] = parent[(int) parent[(int) x]];
			x = parent[(int) x];
		}
		return x;
	}
	static long min(long a, long b, long c){
		if(a<b && a<c) return a;
		if(b<c) return b;
		return c;
	}
	/*
	static void dfs3D(int x,int y,int z){
		ans++;
		boo[x][y][z] = true;
		for(Pair3 e:pmp[x][y][z]){
			if(!boo[e.x][e.y][e.z]){
				dfs3D(e.x,e.y,e.z);
			}
		}
	}
	static class Pair3{
		int x, y ,z;
		Pair3(int x, int y, int z){
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}*/
	static int sum(int n){
		String str = Integer.toString(n);
		int cnt = 0;
		for(int i = 0; i< str.length();i++){
			cnt+=(str.charAt(i)-'0');
		}
		return cnt;
	}
	 static void KMPSearch(String pat, String txt)
	    {
	        int M = pat.length();
	        int N = txt.length();
	 
	        // create lps[] that will hold the longest
	        // prefix suffix values for pattern
	        int lps[] = new int[M];
	        int j = 0;  // index for pat[]
	 
	        // Preprocess the pattern (calculate lps[]
	        // array)
	        computeLPSArray(pat,M,lps);
	 
	        int i = 0;  // index for txt[]
	        while (i < N)
	        {
	            if (pat.charAt(j) == txt.charAt(i))
	            {
	                j++;
	                i++;
	            }
	            if (j == M)
	            {
	               // parent.add((i-j));
	                j = lps[j-1];
	            }
	 
	            // mismatch after j matches
	            else if (i < N && pat.charAt(j) != txt.charAt(i))
	            {
	                // Do not match lps[0..lps[j-1]] characters,
	                // they will match anyway
	                if (j != 0)
	                    j = lps[j-1];
	                else
	                    i = i+1;
	            }
	        }
	    }
	 static void computeLPSArray(String pat, int M, int lps[])
	    {
	        // length of the previous longest prefix suffix
	        int len = 0;
	        int i = 1;
	        lps[0] = 0;  // lps[0] is always 0
	 
	        // the loop calculates lps[i] for i = 1 to M-1
	        while (i < M)
	        {
	            if (pat.charAt(i) == pat.charAt(len))
	            {
	                len++;
	                lps[i] = len;
	                i++;
	            }
	            else  // (pat[i] != pat[len])
	            {
	                // This is tricky. Consider the example.
	                // AAACAAAA and i = 7. The idea is similar 
	                // to search step.
	                if (len != 0)
	                {
	                    len = lps[len-1];
	 
	                    // Also, note that we do not increment
	                    // i here
	                }
	                else  // if (len == 0)
	                {
	                    lps[i] = len;
	                    i++;
	                }
	            }
	        }
	    }
	private static void permutation(String prefix, String str) {
	    int n = str.length();
	    if (n == 0); //hs.add(prefix);
	    else {
	        for (int i = 0; i < n; i++)
	            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
	    }
	}
	public static char give(char c1,char c2){
		if(c1!='a' && c2!='a') return 'a';
		if(c1!='b' && c2!='b') return 'b';
		return 'c';
	}
	static class Graph{
		int vertex;
		long weight;
	}
	public static void buildTree(int n){
		int arr[] = sc.nextIntArray(n);
		for(int i = 0;i<n;i++){
			int x = arr[i]-1;
			amp[i+1].add(x);
			amp[x].add(i+1);
		}
	}
	
	
	static class SegmentTree{
		int pre[], suf[], max[], val[];
		SegmentTree( int n){
			int size = 4*n;
			pre = new int[size];
			suf = new int[size];
			max = new int[size];
			val = new int[size];
			build(0,n-1,1);
		}
		void build(int ss, int se, int si){
			if(ss==se){
				pre[si] = 1;
				suf[si] = 1;
				max[si] = 1;
				val[si] = arr[ss];
			}
			else{
			int mid = (ss+se)>>2;
			si*=2;
			build(ss,mid,si);build(mid+1,se,si+1);
			}
		}
		
		/*int[] get(int qs, int qe, int ss, int se, int si){
			if(qe < ss || se < qs)
        		return new int[2];
			if(qs<=ss && qe>=se){
				return new int[]{max[si],val[si]};
			}
			int mid = (ss+se)/2;
			si*=2;
			if(qe<=mid) return get(qs,qe,ss,mid,si);
			else if(qs>mid) return get(qs,qe,mid+1,se,si+1);
			long a1[] = build(ss,mid,si*2), a2[] = build(mid+1,se,si*2+1);
			long ans[] = new long[4];
			if(arr[mid] == arr[mid+1]){
			    long temp = a1[2]+a2[0];
			    if(temp>=a2[1] && temp>=a1[1]){
			        ans[1] = temp;
			        ans[3] = arr[mid];
			    }
			    else if(a2[1]>=a1[1]){
			        ans[1] = a2[1];
			        ans[3] = a2[3];
			    }
			    else{
			        ans[1] = a1[1];
			        ans[3] = a1[3];
			    } 
			    if(a1[1]==(mid-ss+1)) ans[0] = ans[1];
			    else ans[0] = a1[0];
			    if(a2[2]==(se-mid)) ans[2] = ans[1];
				else ans[2] = a2[2];
			}
			else{
				if(a2[1]>=a1[1]){
			        ans[1] = a2[1];
			        ans[3] = a2[3];
			    }
			    else{
			        ans[1] = a1[1];
			        ans[3] = a1[3];
			    } 
				ans[0] = a1[0];
				ans[2] = a2[2];
			}
            return ans;
		}
		void print(){
			for(int i = 0;i<st.length;i++){
				System.out.println(st[i][0]+" "+st[i][1]+" "+st[i][2]+" "+st[i][3]);
			}
			System.out.println();
		}*/
	}
	static int convert(int x){
		int cnt = 0;
		String str = Integer.toBinaryString(x);
		//System.out.println(str);
		for(int i = 0;i<str.length();i++){
			if(str.charAt(i)=='1'){
				cnt++;
			}
		}
		int ans = (int) Math.pow(3, 6-cnt);
		return ans;
	}
	static class Node2{
		Node2 left = null;
		Node2 right = null;
		Node2 parent = null;
		int data;
	}
	static class BinarySearchTree{
		Node2 root = null;
		int height = 0;
		int max = 0;
		int cnt = 1;
		ArrayList<Integer> parent = new ArrayList<>();
		HashMap<Integer, Integer> hm = new HashMap<>();
		public void insert(int x){
			Node2 n = new Node2();
			n.data = x;
			if(root==null){
				root = n;
			}
			else{
				Node2 temp = root,temp2 = null;
				while(temp!=null){
					temp2 = temp;
					if(x>temp.data) temp = temp.right;
					else temp = temp.left;
				}
				if(x>temp2.data) temp2.right = n;
				else temp2.left = n;
				n.parent = temp2;
				parent.add(temp2.data);
			}
		}
		public Node2 getSomething(int x, int y, Node2 n){
			if(n.data==x || n.data==y) return n;
			else if(n.data>x && n.data<y) return n;
			else if(n.data<x && n.data<y) return getSomething(x,y,n.right);
			else return getSomething(x,y,n.left);
		}
		public Node2 search(int x,Node2 n){
			if(x==n.data){
				max = Math.max(max, n.data);
				return n;
			}
			if(x>n.data){
				max = Math.max(max, n.data);
				return search(x,n.right);
			}
			else{
				max = Math.max(max, n.data);
				return search(x,n.left);
			}
		}
		public int getHeight(Node2 n){
			if(n==null) return 0;
			height = 1+ Math.max(getHeight(n.left), getHeight(n.right));
			return height;
		}
	}
	static long findDiff(long[] arr, long[] brr, int m){
		int i = 0, j = 0;
		long fa = 1000000000000L;
		while(i<m && j<m){
			long x = arr[i]-brr[j];
			if(x>=0){
				if(x<fa) fa = x;
				j++;
			}
			else{
				if((-x)<fa) fa = -x;
				i++;
			}
		}
		return fa;
	}
	public static long max(long x, long y, long z){
		if(x>=y && x>=z) return x;
		if(y>=x && y>=z) return y;
		return z;
	}
	
	public static void seive(long n){
		b = new boolean[(int) (n+1)];
		Arrays.fill(b, true);
		for(int i = 2;i*i<=n;i++){
			if(b[i]){
				for(int p = 2*i;p<=n;p+=i){
					b[p] = false;
				}
			}
		}
	}
	static long modInverse(long a, long mOD2){
	            return  power(a, mOD2-2, mOD2);
	}
	static long power(long x, long y, long m)
	{
	    if (y == 0)
	        return 1;
	    long p = power(x, y/2, m) % m;
	    p = (p * p) % m;
	 
	    return (y%2 == 0)? p : (x * p) % m;
	}
	static long power2(long x,BigInteger y,long m){
		long ans = 1;
		BigInteger two = new BigInteger("2");
		while(y.compareTo(BigInteger.ZERO)>0){
			if(y.getLowestSetBit()==y.bitCount()){
				x = (x*x)%MOD;
				y = y.divide(two);
			}
			else{
				ans = (ans*x)%MOD;
				y = y.subtract(BigInteger.ONE);
			}
		}
		return ans;
	}
	static BigInteger power2(BigInteger x, BigInteger y, BigInteger m){
		BigInteger ans = new BigInteger("1");
		BigInteger one  = new BigInteger("1");
		BigInteger two  = new BigInteger("2");
		BigInteger zero  = new BigInteger("0");
		while(y.compareTo(zero)>0){
			//System.out.println(y);
			if(y.mod(two).equals(one)){
				ans = ans.multiply(x).mod(m);
				y = y.subtract(one);
			}
			else{
				x = x.multiply(x).mod(m);
				y = y.divide(two);
			}
		}
		return ans;
	}
	static BigInteger power(BigInteger x, BigInteger y, BigInteger m)
	{
	    if (y.equals(0))
	        return (new BigInteger("1"));
	    BigInteger p = power(x, y.divide(new BigInteger("2")), m).mod(m);
	    p = (p.multiply(p)).mod(m);
	 
	    return (y.mod(new BigInteger("2")).equals(0))? p : (p.multiply(x)).mod(m);
	}
	static long d,x,y;
	public static void extendedEuclidian(long a, long b){
		if(b == 0) {
	        d = a;
	        x = 1;
	        y = 0;
	    }
	    else {
	        extendedEuclidian(b, a%b);
	        int temp = (int) x;
	        x = y;
	        y = temp - (a/b)*y;
	    }
	}
	
	public static long gcd(long n, long m){
		if(m!=0) return gcd(m,n%m);
		else return n;
	}
	
	
	public static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
 
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = System.in.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
 
		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	        
	    public int[] nextIntArray(int n) {
	        return nextIntArray(n, 0);
	    }
	    
	    public int[] nextIntArray(int n, int off) {
	    	int[] arr = new int[n + off];
	    	for (int i = 0; i < n; i++) {
	    		arr[i + off] = nextInt();
	    	}
	    	return arr;
	    }
	    
	    public long[] nextLongArray(int n) {
	    	return nextLongArray(n, 0);
	    }
        
		public long[] nextLongArray(int n, int off) {
		    long[] arr = new long[n + off];
		    for (int i = 0; i < n; i++) {
		        arr[i + off] = nextLong();
		    }
		    return arr;
		}
 
	    private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
	}
}