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

public class _v10 {

    public static void main(String args[]){

        PrintWriter out = new PrintWriter(System.out);
        Reader in = new Reader();
        int n  = in.nextInt();
        int f[] = new int[n+1];
        int g[] = new int[n+1];
        Dsu dsu = new Dsu(n);
        for(int i=1;i<=n;i++){
            f[i] = in.nextInt();
            dsu.union(i,f[i]);
        }

        int m = 0;

        int par[] = dsu.par;
        Map<Integer,Integer> map = new HashMap<>();
        int count = 1;
        for(int i=1;i<=n;i++){
              g[i] = dsu.find(i);
              if(!map.containsKey(g[i])){
                  map.put(g[i],count++);
              }

             if(par[i]==i){
                m++;


            }
        }

        for(int i=1;i<=n;i++){
            g[i] = map.get(g[i]);
        }

        int h[] = new int[m+1];
        int tf[] = new int[n+1];

        for(int i=1;i<=n;i++){
            h[g[i]] = f[i];

        }

        for(int i=1;i<=n;i++){
            tf[f[i]] = 1;

        }


        for(int i=1;i<=m;i++){
            if(tf[h[i]] == 1){
                tf[h[i]] = 0;
            }
        }

        for(int i=1;i<=n;i++){
            if(tf[i] == 1){
                out.println(-1);
                out.flush();
                out.close();
                return;
            }
        }



        out.println(m);
        for(int i=1;i<=n;i++){
            out.print(g[i]+" ");
        }
        out.println();

        for(int i=1;i<=m;i++){
            out.print(h[i]+" ");
        }
        out.flush();
        out.close();
    }

    static class Dsu{
        int par[];
        int size[];

        Dsu(int n){
            par = new int[n+1];
            size = new int[n+1];
            Arrays.fill(size,1);

            for(int i=1;i<=n;i++){
                par[i] = i;
            }
        }
        int find(int x){
            if(par[x]==x){
                return x;
            }

            int temp = find(par[x]);
            par[x] = temp;

            return temp;
        }

        boolean union(int x,int y){

            int parx = find(x);
            int pary = find(y);

            if(parx == pary){
                return false;
            }


            if(size[parx] >= size[pary]){
                size[parx] += size[pary];
                par[pary] = parx;
            }
            else{
                size[pary] += size[parx];
                par[parx] = pary;
            }


            return true;
        }

    }
    static class Reader {

        private InputStream mIs;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public Reader() {
            this(System.in);
        }

        public Reader(InputStream is) {
            mIs = is;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();

            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = mIs.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

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

        public boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

    }

}