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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Main {
	final int _intMax = Integer.MAX_VALUE; //=2147483647>10^9
	final long _longMax = Long.MAX_VALUE; //=9223372036854775807L>10^18
	static boolean bElapsed = false;
	StringBuilder sb = new StringBuilder();
	List<String> list = new ArrayList<>();
	Set<String> set = new HashSet<>();
	Map<String,String> map = new HashMap<>();
	Queue<String> queue = new ArrayDeque<>();
	Deque<String> stack = new ArrayDeque<>();

	void solve() {
		int n = readNum();
		int[] num = readNums();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] r = new int[n];
		for (int i=1; i<=n; i++) {
			r[num[i-1]-1] = i;
		}
		for (int i=1; i<=n; i++) {
			a[i-1] = 30000*i;
			b[i-1] = 30000*(n-i+1)+r[i-1];
		}
		for (int i=0; i<n; i++) {
			sb.append(a[i]).append(" ");
		}
		sb.deleteCharAt(sb.length()-1);
		pln(sb.toString());
		sb.delete(0, sb.length());
		for (int i=0; i<n; i++) {
			sb.append(b[i]).append(" ");
		}
		sb.deleteCharAt(sb.length()-1);
		pln(sb.toString());
	}

	class Point {
		int x;
		int y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		public boolean equals(Object o) {
			if (o instanceof Point) {
				Point that = (Point)o;
				return (x == that.x) && (y == that.y);
			}
			return false;
		}
		public int hashCode() {
			return x + (y << 16);
		}
		public String toString() {
			return "(" + x + ", " + y + ")";
		}
	}
	class Info implements Comparable<Info> {
		int idx;
		int val;
		public Info(int idx, int val) {
			this.idx = idx;
			this.val = val;
		}
		public int compareTo(Info o) {
			return idx - o.idx;
		}
		public boolean equals(Object o) {
			if (o instanceof Info) {
				Info that = (Info)o;
				return 0 == compareTo(that);
			}
			return false;
		}
		public int hashCode() {
			return idx + (val << 16);
		}
		public String toString() {
			return "(" + idx + ", " + val + ")";
		}
	}
	class InfoComp implements Comparator<Info> {
		public int compare(Info o1, Info o2) {
			return o1.val - o2.val;
		}
	}
	int pint(String s) {
		return Integer.parseInt(s);
	}
	String readLine() {
		try {
			_line = _in.readLine();
			return _line;
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}
	int readNum() {
		readLine();
		return pint(_line);
	}
	String[] readFields() {
		readLine();
		_flds = _line.split(" ");
		return _flds;
	}
	int[] readNums() {
		readFields();
		_nums = new int[_flds.length];
		for (int i=0; i<_flds.length; i++) {
			_nums[i] = pint(_flds[i]);
		}
		return _nums;
	}
	void p(char c) {
		_out.print(c);
	}
	void pln(char c) {
		_out.println(c);
	}
	void p(double d) {
		_out.print(d);
	}
	void pln(double d) {
		_out.println(d);
	}
	void p(long l) {
		_out.print(l);
	}
	void pln(long l) {
		_out.println(l);
	}
	void p(String s) {
		_out.print(s);
	}
	void pln(String s) {
		_out.println(s);
	}
	String _line;
	String[] _flds;
	int[] _nums;
	static BufferedReader _in;
	static PrintWriter _out;
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		_in = new BufferedReader(new InputStreamReader(System.in));
		_out = new PrintWriter(System.out);
		new Main().solve();
		_out.flush();
		long end = System.currentTimeMillis();
		if (bElapsed) {
			System.err.println((end-start) + "ms");
		}
	}
}