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.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class CFA1 
{


	static int n;
	static int f[];
	static int g[];
	static int h[];



	public static void main(String[]args)throws Throwable
	{
		SC sc = new SC(System.in);
		n = sc.nextInt();
		PrintWriter out = new PrintWriter(System.out);

		f = new int[n + 1];
		TreeMap<Integer,Integer> gMap = new TreeMap();
		TreeMap<Integer,Integer> hMap = new TreeMap();
		int cnt = 1;
		for(int i = 1 ; i <= n ; ++i)
		{
			f[i] = sc.nextInt();
			if(gMap.containsKey(f[i]))
				continue;
			gMap.put(f[i],cnt);
			hMap.put(cnt,f[i]);
			++cnt;
		}
		g = new int[n + 1];
		h = new int[cnt + 1];
		for(int i = 1 ; i <= n ; ++i)
		{
			g[i] = gMap.get(f[i]);
			
		}
		
		for(int i = 1 ;i < cnt ; ++i)
		{
			h[i] = hMap.get(i);
		
		}
		for(int i = 1 ; i < cnt ; ++i)
		{
			if(g[h[i]] != i)
			{
				out.print("-1");
				out.flush();
				out.close();
				return;
			}
		}
		for(int i = 1 ; i <= n ; ++i)
		{
			if(h[g[i]] != f[i])
			{
				out.println("-1");
				out.flush();
				out.close();
				return;
			}
		}
		out.println(cnt - 1);
		for(int i = 1 ; i <= n ; ++i)
		{
		
			out.print(g[i]+" ");
		}
		out.println("");
		for(int i = 1 ;i < cnt ; ++i)
		{
	
			out.print(h[i]+" ");
		}
		out.flush();
		out.close();

	}

	static class SC
	{
		BufferedReader br;
		StringTokenizer st;


		SC(InputStream s)  { br = new BufferedReader(new InputStreamReader(s)); }

		String next() throws IOException
		{
			while(st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();

		}

		int nextInt() throws NumberFormatException, IOException { return Integer.parseInt(next()); }

	}
}