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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;
import java.util.regex.Matcher;
import java.util.regex.Pattern;



public class CF397D {

    static StringTokenizer st;
    static BufferedReader br;
    static PrintWriter pw;

    static class Sort implements Comparable<Sort> {
        int ind, a;

        @Override
        public int compareTo(Sort o) {
            return a - o.a;
        }
        public Sort(int i, int an) {
            ind = i;
            a = an;
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        solve();
        pw.close();
    }
    
    static int n, m;
    static int[] f, g, h, ind;
    
    private static void solve() throws IOException {
    	n = nextInt();
    	f = new int [n + 1];
    	g = new int [n + 1];
    	h = new int [n + 1];
    	ind = new int [n + 1];
    	m = 0;
    	for (int i = 1; i <= n; ++i)
    		f[i] = nextInt();
    	for (int i = 1; i <= n; ++i) {
    		if (ind[f[i]] == 0) {
    			ind[f[i]] = ++m;
    			g[i] = ind[f[i]];
    			h[m] = f[i];
    		} else {
    			g[i] = ind[f[i]];
    		}
    	}
    	for (int i = 1; i <= m; ++i) {
    		if (g[h[i]] != i) {
    			pw.println(-1);
    			return;
    		}
    	}
    	pw.println(m);
    	for (int i = 1; i <= n; ++i)
    		pw.print(g[i] + " ");
    	pw.println();
    	for (int i = 1; i <= m; ++i)
    		pw.print(h[i] + " ");
    }

	private static int sumf(int[] fen, int id) {
        int summ = 0;
        for (; id >= 0; id = (id & (id + 1)) - 1)
            summ += fen[id];
        return summ;
    }

    private static void addf(int[] fen, int id) {
        for (; id < fen.length; id |= id + 1)
            fen[id]++;
    }

    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    private static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    private static String next() throws IOException {
        while (st==null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
}