Problem: You are given a permutation p of the set {1, 2, ..., N}. Please construct two sequences of positive integers a_1, a_2, ..., a_N and b_1, b_2, ..., b_N satisfying the following conditions:

* 1 \leq a_i, b_i \leq 10^9 for all i
* a_1 < a_2 < ... < a_N
* b_1 > b_2 > ... > b_N
* a_{p_1}+b_{p_1} < a_{p_2}+b_{p_2} < ... < a_{p_N}+b_{p_N}

Constraints

* 2 \leq N \leq 20,000
* p is a permutation of the set {1, 2, ..., N}

Input

The input is given from Standard Input in the following format:


N
p_1 p_2 ... p_N


Output

The output consists of two lines. The first line contains a_1, a_2, ..., a_N seperated by a space. The second line contains b_1, b_2, ..., b_N seperated by a space.

It can be shown that there always exists a solution for any input satisfying the constraints.

Examples

Input

2
1 2


Output

1 4
5 4


Input

3
3 2 1


Output

1 2 3
5 3 1


Input

3
2 3 1


Output

5 10 100
100 10 1

Solution (in JAVA):

Solution:

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;


public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int[] p = sc.nextIntList(N);
		StarrySkyTree a = new StarrySkyTree(N + 1);
		StarrySkyTree b = new StarrySkyTree(N + 1);
		for (int i = 1; i <= N;i ++) {
			a.add(i, i + 1, i);
			b.add(i, i + 1, N - i + 1);
		}

		int now = N;
		for (int v : p) {
			a.add(v + 1, N + 1, now);
			b.add(1, v, now);
			now --;
		}
		
		StringBuilder sa = new StringBuilder();
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= N; i ++) {
			sa.append(a.min(i, i + 1));
			sa.append(" ");
			sb.append(b.min(i, i + 1));
			sb.append(" ");
		}
		
		System.out.println(sa.substring(0, sa.length() - 1));
		System.out.println(sb.substring(0, sb.length() - 1));
	}
}

class StarrySkyTree {
	public int M, H, N;
	public int[] st;
	public int[] plus;
	public int I = Integer.MAX_VALUE/4; // I+plus<int
	
	public StarrySkyTree(int n)
	{
		N = n;
		M = Integer.highestOneBit(Math.max(n-1, 1))<<2;
		H = M>>>1;
		st = new int[M];
		plus = new int[H];
	}
	
	public StarrySkyTree(int[] a)
	{
		N = a.length;
		M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
		H = M>>>1;
		st = new int[M];
		for(int i = 0;i < N;i++){
			st[H+i] = a[i];
		}
		plus = new int[H];
		Arrays.fill(st, H+N, M, I);
		for(int i = H-1;i >= 1;i--)propagate(i);
	}
	
	private void propagate(int i)
	{
		st[i] = Math.min(st[2*i], st[2*i+1]) + plus[i];
	}
	
	public void add(int l, int r, int v){ if(l < r)add(l, r, v, 0, H, 1); }
	
	private void add(int l, int r, int v, int cl, int cr, int cur)
	{
		if(l <= cl && cr <= r){
			if(cur >= H){
				st[cur] += v;
			}else{
				plus[cur] += v;
				propagate(cur);
			}
		}else{
			int mid = cl+cr>>>1;
			if(cl < r && l < mid){
				add(l, r, v, cl, mid, 2*cur);
			}
			if(mid < r && l < cr){
				add(l, r, v, mid, cr, 2*cur+1);
			}
			propagate(cur);
		}
	}
	
	public int min(int l, int r){ return l >= r ? I : min(l, r, 0, H, 1);}
	
	private int min(int l, int r, int cl, int cr, int cur)
	{
		if(l <= cl && cr <= r){
			return st[cur];
		}else{
			int mid = cl+cr>>>1;
			int ret = I;
			if(cl < r && l < mid){
				ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
			}
			if(mid < r && l < cr){
				ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
			}
			return ret + plus[cur];
		}
	}
	
	public int[] toArray() { return toArray(1, 0, H, new int[H]); }
	
	private int[] toArray(int cur, int l, int r, int[] ret)
	{
		if(r-l == 1){
			ret[cur-H] = st[cur];
		}else{
			toArray(2*cur, l, l+r>>>1, ret);
			toArray(2*cur+1, l+r>>>1, r, ret);
			for(int i = l;i < r;i++)ret[i] += plus[cur];
		}
		return ret;
	}
}


class FastScanner {
	public static String debug = null;

	private final InputStream in = System.in;
	private int ptr = 0;
	private int buflen = 0;
	private byte[] buffer = new byte[1024];
	private boolean eos = false;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				if (debug != null) {
					buflen = debug.length();
					buffer = debug.getBytes();
					debug = "";
					eos = true;
				} else {
					buflen = in.read(buffer);
				}
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen < 0) {
				eos = true;
				return false;
			} else if (buflen == 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	public boolean isEOS() {
		return this.eos;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		return (int) nextLong();
	}

	public long[] nextLongList(int n) {
		return nextLongTable(1, n)[0];
	}

	public int[] nextIntList(int n) {
		return nextIntTable(1, n)[0];
	}

	public long[][] nextLongTable(int n, int m) {
		long[][] ret = new long[n][m];
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				ret[i][j] = nextLong();
			}
		}
		return ret;
	}

	public int[][] nextIntTable(int n, int m) {
		int[][] ret = new int[n][m];
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				ret[i][j] = nextInt();
			}
		}
		return ret;
	}
}