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.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Locale;
import java.util.PriorityQueue;


public class d
{
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static String readln() throws IOException
    {
        String line = input.readLine();
        return line;
    }

    public static void main(String[] args) throws IOException
    {
        Locale.setDefault(Locale.US);
        int s = Integer.parseInt(d.readln());
        String[] input = d.readln().split(" ");
        
        int[] f = new int[s + 1];
        
        for(int i = 1; i <= s; i++){
        	f[i] = Integer.parseInt(input[i - 1]);
        }
        
        HashSet<Integer> cnt = new HashSet<Integer>();
        
        for(int i = 1; i <= s; i++){
        	cnt.add(f[i]);
        }
        
        int m = cnt.size();
        		
        int[] h = new int[m + 1];
        
        PriorityQueue<Integer> order = new PriorityQueue(cnt);
        
        for(int i = 1; i <= m; i++){
        	h[i] = order.poll();
        }
        
        
        int[] g = new int[s + 1];
        
        //h[g[s]] = f[s]
        HashMap<Integer, Integer> hi = new HashMap<Integer, Integer>();
        
        for(int i = 1; i <= m; i++){
        	hi.put(h[i], i);
        }
        
        for(int i = 1; i <= s; i ++){
        	g[i] = hi.get(f[i]);
        }
        
        for(int i = 1; i <= m; i++){
        	try{
        		if(g[h[i]] != i){
        		System.out.println(-1);
        		return;
        		}
        	} catch (Exception e){
        		System.out.println(-1);
        		return;
        	}
        }
        
        System.out.println(m);
        for(int i = 1; i <= s; i ++){
        	System.out.print(g[i] + " ");
        }
        System.out.println();
        
        for(int i = 1; i <= m; i ++){
        	System.out.print(h[i] + " ") ;
        }
        System.out.println();
        
        //so h[m] needs to have the same range of the output h[s] - if not' it's impossible
        
        //so g[s] has to provide enough different outputs that it can be mapped to the outputs of h[s]
        
        //if h == g, g[h[m]] = m
        
        
    }  
}