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 CPP):

Solution:
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-6;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
inline int scan(int &a) { return scanf("%d", &a); }
inline int scan(int &a, int &b) { return scanf("%d%d", &a, &b); }
inline int scan(int &a, int &b, int &c) { return scanf("%d%d%d", &a, &b, &c); }
inline int scan(long long &a) { return scanf("%I64d", &a); }
inline int scan(long long &a, long long &b) {
  return scanf("%I64d%I64d", &a, &b);
}
inline int scan(long long &a, long long &b, long long &c) {
  return scanf("%I64d%I64d%I64d", &a, &b, &c);
}
inline int scan(double &a) { return scanf("%lf", &a); }
inline int scan(double &a, double &b) { return scanf("%lf%lf", &a, &b); }
inline int scan(double &a, double &b, double &c) {
  return scanf("%lf%lf%lf", &a, &b, &c);
}
inline int scan(char &a) { return scanf("%c", &a); }
inline int scan(char *a) { return scanf("%s", a); }
template <class T>
inline void mem(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T0, class T1>
inline void mem(T0 &A0, T1 &A1, int x) {
  mem(A0, x), mem(A1, x);
}
template <class T0, class T1, class T2>
inline void mem(T0 &A0, T1 &A1, T2 &A2, int x) {
  mem(A0, x), mem(A1, x), mem(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x), mem(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x), mem(A4, x), mem(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x), mem(A4, x), mem(A5, x),
      mem(A6, x);
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T min(T a, T b, T c, T d, T e) {
  return min(min(min(a, b), min(c, d)), e);
}
template <class T>
inline T max(T a, T b, T c, T d, T e) {
  return max(max(max(a, b), max(c, d)), e);
}
int f[maxn], g[maxn], h[maxn], pos[maxn];
int main() {
  int m;
  while (~scan(m)) {
    mem(g, pos, -1);
    int n = 0;
    for (int i = 1; i < m + 1; i++) {
      scan(f[i]);
      if (f[i] == i) h[++n] = i, g[i] = n, pos[i] = i;
    }
    if (!n)
      puts("-1");
    else {
      int flag = 0;
      for (int i = 1; i < m + 1; i++) {
        if (g[i] == -1) {
          if (pos[f[i]] == -1)
            flag = 1;
          else
            g[i] = g[pos[f[i]]];
        }
      }
      if (flag)
        puts("-1");
      else {
        printf("%d\n", n);
        for (int i = 1; i < m + 1; i++)
          printf("%d%c", g[i], i == m ? '\n' : ' ');
        for (int i = 1; i < n + 1; i++)
          printf("%d%c", h[i], i == n ? '\n' : ' ');
      }
    }
  }
  return 0;
}