#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

You are given a permutation *P* of length *N*. Construct two sequences *A* and *B* of length *N* such that:

- 1 ≤ A
_{i}, B_{i}≤ 10^{9}, - A is strictly increasing,
- B is strictly decreasing,
- the sequence defined by (A
_{Pi}+ B_{Pi}) 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, |A_{i}|, |B_{i}| ≤ 10^{18}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 14 | 22 | 1s | 256MB | Minimum |

2 | 20 | 42 | 1s | 256MB | Minimum |

3 | 21 | 62 | 1s | 256MB | Minimum |

4 | 22 | 62 | 1s | 256MB | Minimum |

5 | 23 | 62 | 1s | 256MB | Minimum |

6 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o construct -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512