Problem Description

You are given an array of $n$ integers $a_1, a_2, ..., a_n$. We define that a sequence $p_1, p_2, ..., p_k(k \in [1,n])$ is beautiful if and only if these conditions are met:

$\quad$ $\bullet$ $1 \le p_1 < p_2<\cdots<p_k \le n. $

$\quad$ $\bullet$ There exists $t(t \in [1,k])$ satisfying $a_{p_1}<a_{p_2}<\cdots<a_{p_t}$ and $a_{p_t}>a_{p_{t+1}} > \cdots > a_{p_k}$.

You need to find all the longest beautiful sequences, and output the lexicographically smallest one and the lexicographically largest one in them.

Check the examples below for better understanding.

Input

There are multiple test cases.

Each case starts with a line containing a positive integer $n(n \leq 3 \times 10^5)$.

The second line contains $n$ integers $a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9)$.

It is guaranteed that the sum of $N$s in all test cases is no larger than $10^6$.

Output

For each test case, output two lines, the first of which depicts the lexicographically smallest one in longest beautiful sequences and the second of which depicts the lexicographically largest one in longest beautiful sequences.

7
1 4 2 5 7 4 6
3
1 2 3
3
3 2 1

1 2 4 5 6
1 3 4 5 7
1 2 3
1 2 3
1 2 3
1 2 3