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.util.*;

public class ProbD {
	public static void main(String[] args) {
		ProbD sol = new ProbD();
		sol.start();
	}

	public void print(Object o){ System.out.print(o); }
	public void println(Object o) { System.out.println(o); }

	public void start(){
		submit();
	}
	
	public void submit(){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] f = new int[n];
		for(int i=0;i<n;i++) f[i] = scan.nextInt() - 1;
		scan.close();
		
		decompose(f);
		System.out.flush();
	}
	
	public void decompose(int[] f){
		int n = f.length, m = numberOfElements(f);
		int[] g = new int[n], h = new int[m];
		int tmp = 0;
		for(int i=0;i<n;i++) if(f[i]==i) {
			h[tmp] = i;
			g[i] = tmp;
			tmp++;
		}
		if(tmp<m){
			System.out.println(-1);
			return;
		}
		for(int i=0;i<n;i++){
			g[i] = g[f[i]];
		}
		System.out.println(m);
		for(int i : g) System.out.print((i+1)+" ");
		System.out.println();
		for(int i : h) System.out.print((i+1)+" ");
		System.out.println();
	}
	
	private int numberOfElements(int[] f){
		int n = f.length;
		boolean[] mark = new boolean[n];
		int ret = 0;
		Arrays.fill(mark, false);
		for(int i : f){
			if(mark[i]) continue;
			ret += 1;
			mark[i] = true;
		}
		return ret;
	}
}