Problem Description
You are given a permutation P of length N. Construct two sequences A and B of length N such that:
- 1 ≤ Ai, Bi ≤ 109,
- A is strictly increasing,
- B is strictly decreasing,
- the sequence defined by (APi + BPi) is strictly increasing.
It is guaranteed that there exists a solution.
Limits
Subtask 1 (14%): 1 ≤ N ≤ 3.
Subtask 2 (20%): 1 ≤ N ≤ 70.
Subtask 3 (21%): 1 ≤ N ≤ 50 000, the bound on a strictly decreasing B is removed.
Subtask 4 (22%): 1 ≤ N ≤ 50 000, |Ai|, |Bi| ≤ 1018.
Subtask 5 (23%): 1 ≤ N ≤ 50 000.
Subtask 6 (0%): Sample Testcases.
Input
The first line of input will contain one integer, N.
The second line of input will contain N integers, representing the permutation P.
Output
The first line of output should contain N integers, the sequence A.
The second line of output should contain N integers, the sequence B.
If there are multiple solutions, all of them will be accepted.
Sample Testcase 1
Input
2
1 2
Output
1 4
5 4
Sample Testcase 2
Input
3
2 3 1
Output
5 10 100
100 10 1