The OLP-ICPC 2022 contest is the first time that UMT has participated. Under the guidance of Mr. Trung, the team has had memorable and rewarding experiences. After 2 more years of participation in Hue and Hanoi as well as exciting activities at the Algorithm Club, UMT's ICPC teams have significantly increased their fighting power. Recalling the intense review period, the UMT.Individual team shared a problem that was both strange and familiar, introduced by Mr.Trung, which left a lasting impression on them. That is a classic concept in programming: the Longest Increasing Subsequence (LIS).

You are given an array of integers ~A~ consisting of ~N~ elements. For each index ~i~ in the array, determine the following:

• The length of the longest increasing subsequence that ends at position ~i~.

• The length of the longest increasing subsequence that starts at position ~i~.

An increasing subsequence is a sequence of elements (not necessarily contiguous) from the original array, arranged in strictly increasing order (each element is greater than the one before it). The length of a subsequence is defined as the number of elements it contains.

Input

• The first line contains an integer ~N~ ~(1 ≤ N ≤ 10^6)~, the number of elements in the sequence.

• The second line contains ~N~ integers ~A_i~ ~(1 ≤ A_i ≤ 10^9)~, the elements of the sequence.

Output

The output consists of two lines, each containing ~N~ integers.

• The ~i^{th}~ number in the first line represents the length of the longest increasing subsequence ending at position ~i~.

• The ~i^{th}~ number in the second line represents the length of the longest increasing subsequence starting at position ~i~.

Sample Input 1

5
1 9 6 7 6

Sample Ouput 1

1 2 2 3 2
3 1 2 1 1

Note:

• At position 1, the longest increasing subsequences ending and starting here are: [1] and [1, 6, 7].

• At position 2, the longest increasing subsequences ending and starting here are: [1, 9] and [9].

• At position 3, the longest increasing subsequences ending and starting here are: [1, 6] and [6, 7].

• At position 4, the longest increasing subsequences ending and starting here are: [1, 6, 7] and [7].

• At position 5, the longest increasing subsequences ending and starting here are: [1, 6] and [6].