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.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.HashSet;
import java.util.ArrayList;
public class Main{
  public static class InputReader {
    BufferedReader reader;
    StringTokenizer tokenizer;
    
    public InputReader (InputStream stream){
      reader = new BufferedReader(new InputStreamReader(stream));
    }
    
    public String next(){
      while(tokenizer == null || !tokenizer.hasMoreTokens()){
        try{
          String line = reader.readLine();
          if(line == null){
            return "0";
          }
          tokenizer = new StringTokenizer(line);
        } catch(IOException ioe){
          throw new RuntimeException(ioe);
        }
      }
      return tokenizer.nextToken();
    }
    
    public int nextInt(){
      return Integer.parseInt(next());
    }
    
    public double nextDouble(){
      return Double.parseDouble(next());
    }
    
    public Long nextLong(){
      return Long.parseLong(next());
    }
    
    public BigInteger nextBigInteger(){
      return new BigInteger(next());
    }
    
    public String nextLine(){
      String line = "";
      try{
        while(line.equals("")){
          line = reader.readLine();
        }
      } catch(IOException ioe){
        throw new RuntimeException(ioe);
      }
      return line;
    }
  }
  
  public static boolean check(ArrayList<HashSet<Integer> > xToF){
    for(int i=1;i<xToF.size();++i){
      HashSet<Integer> tmp = xToF.get(i);
      if(tmp.size() == 0){
        continue;
      }
      if(!tmp.contains(i)){
        return false;
      }
    }
    return true;
  }
  
  public static void main(String[] argssss){
    InputReader reader = new InputReader(System.in);
    PrintWriter pw = new PrintWriter(System.out);
    int n = reader.nextInt();
    int[] t = new int[n];
    ArrayList<HashSet<Integer> > args = new ArrayList<HashSet<Integer> >(n+1);
    for(int i=0;i<=n;++i){
      args.add(new HashSet<Integer>());
    }
    for(int i=0;i<n;++i){
      t[i] = reader.nextInt();
      args.get(t[i]).add(i+1);
    }
    
    if(!check(args)){
      pw.println("-1");
      pw.flush();
      pw.close();
      return;
    }   
    
    int m = 0;
    for(HashSet<Integer> s : args){
      if(s.size() > 0){
        m++;
      }
    }
    int[] xToM = new int[n+1];
    int[] mToF = new int[m+1];
    int id = 1;
    
    for(int i=0;i<args.size();++i){
      HashSet<Integer> s = args.get(i);
      if(s.size()>0){
        for(Integer arg : s){
          xToM[arg] = id;
        }
        mToF[id] = i;
        id++;
      }
    }
    pw.printf("%d\n", m);
    for(int i=1;i<=n;++i){
      pw.printf("%d ", xToM[i]);
    }
    pw.println();
    for(int i=1;i<=m;++i){
      pw.printf("%d ", mToF[i]);
    }
    pw.flush();
    pw.close();
    
  }
}