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.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class ArtsemSaunders {
    
    int[][] G;
    int[] mark;
    
    void solve() {
        int n = in.nextInt();
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) f[i] = in.nextInt();
        
        for (int i = 1; i <= n; i++) {
            if (f[i] != f[f[i]]) {
                out.println(-1);
                return;
            }
        }
        
        int cnt = 0;
        int[] fr = new int[n], to = new int[n];
        for (int i = 1; i <= n; i++) {
            if (i != f[i]) {
                fr[cnt] = i - 1;
                to[cnt] = f[i] - 1;
                cnt++;
            }
        }
        fr = Arrays.copyOf(fr, cnt);
        to = Arrays.copyOf(to, cnt);
        G = build_graph(n, fr, to);
        
        int m = 0;
        mark = new int[n];
        for (int i = 0; i < n; i++) {
            if (mark[i] == 0) {
                dfs(i, ++m);
            }
        }
        
        int[] g = new int[n + 1];
        for (int i = 1; i <= n; i++) g[i] = mark[i - 1];
        int[] h = new int[m + 1];
        for (int i = 1; i <= n; i++) h[g[i]] = f[i];
        
        out.println(m);
        for (int i = 1; i <= n; i++) {
            if (i > 1) out.print(' ');
            out.print(g[i]);
        }
        out.println();
        for (int i = 1; i <= m; i++) {
            if (i > 1) out.print(' ');
            out.print(h[i]);
        }
    }
    
    void dfs(int u, int color) {
        mark[u] = color;
        for (int v : G[u]) {
            if (mark[v] == 0) {
                dfs(v, color);
            }
        }
    }
    
    int[][] build_graph(int n, int[] from, int[] to) {
        int[][] G = new int[n][];
        int[] cnt = new int[n];
        for (int i = 0; i < from.length; i++) {
            cnt[from[i]]++;
            cnt[to[i]]++;
        }
        for (int i = 0; i < n; i++) G[i] = new int[cnt[i]];
        for (int i = 0; i < from.length; i++) {
            G[from[i]][--cnt[from[i]]] = to[i];
            G[to[i]][--cnt[to[i]]] = from[i];
        }
        return G;
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new ArtsemSaunders().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}