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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rene
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        int[] parent;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int[] f = new int[n + 1];
            int[] g = new int[n + 1];
            int[] h = new int[n + 1];
            int[] minV = new int[n + 1];
            Arrays.fill(minV, n);
            int[] maxV = new int[n + 1];
            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                f[i] = in.nextInt();
                parent[i] = i;
            }
            for (int i = 1; i <= n; i++) join(i, f[i]);
            HashMap<Integer, Integer> component = new HashMap<Integer, Integer>();
            for (int i = 1; i <= n; i++) {
                int compIndex = component.computeIfAbsent(parent[i], v -> component.size() + 1);
                g[i] = compIndex;
                minV[compIndex] = Math.min(minV[compIndex], f[i]);
                maxV[compIndex] = Math.max(maxV[compIndex], f[i]);
                if (f[i] == i) h[compIndex] = i;
            }
            boolean ok = true;
            for (int i = 1; i <= component.size(); i++) ok &= h[i] > 0 && h[i] == minV[i] && h[i] == maxV[i];
            if (ok) {
                out.println(component.size());
                for (int i = 1; i <= n; i++) out.print(g[i] + " ");
                out.println();
                for (int i = 1; i <= component.size(); i++) out.print(h[i] + " ");
                out.println();
            } else out.println(-1);
//        System.out.println("number of components " + component.size());
        }

        public int root(int a) {
            if (a != parent[a]) {
                parent[a] = root(parent[a]);
            }
            return parent[a];
        }

        public void join(int a, int b) {
            parent[root(a)] = root(b);
        }

    }

    static class InputReader implements InputInterface {
        public InputStream stream;
        private int current;
        private int size;
        private byte[] buffer = new byte[10000];

        public InputReader(InputStream stream) {
            this.stream = stream;
            current = 0;
            size = 0;
        }

        public InputReader() {
        }

        int read() {
            int result;
            try {
                if (current >= size) {
                    current = 0;
                    size = stream.read(buffer);
                    if (size < 0) return -1;
                }
            } catch (IOException e) {
                throw new RuntimeException();
            }
            return buffer[current++];
        }


        public int nextInt() {
            int sign = 1;
            int result = 0;
            int c = readNextValid();
            if (c == '-') {
                sign = -1;
                c = read();
            }
            do {
                if (c < '0' || c > '9') throw new RuntimeException();
                result = 10 * result + c - '0';
                c = read();
            } while (!isEmpty(c));
            result *= sign;
            return result;
        }

        private int readNextValid() {
            int result;
            do {
                result = read();
            } while (isEmpty(result));
            return result;
        }

        private boolean isEmpty(int c) {
            return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == -1;
        }

    }

    static interface InputInterface {
    }
}