長さ$N$の数列$A = a_{0}, a_{1}, \cdots, a_{N-1}$の最長増加部分列 (LIS: Longest Increasing Subsequence) のうち、辞書順最小であるものを出力してください。

数列$A$のLISとは、$0 \leq i_0 < i_1 < \cdots < i_k < n$で、$a_{i_0} < a_{i_1} < \cdots < a_{i_k}$を満たすうち、$k$が最も大きいものです。 (つまり、狭義増加のLISです)

辞書順最小とは、$A$の長さ$k$のLISである$X$と$Y$があるとき、全ての$i$($0 \leq i < k$)に対して、$X_i \leq Y_i$が成り立つとき、$X$は数列$A$の辞書順最小であるLISといいます。

制約

• $1 \leq N \leq 2 \times 10^{5}$
• $0 \leq a_i \leq 10^{9}$

入力

入力は以下の形式で標準入力から与えられる。

N
A_0 A_1 .. A_(N-2) A_(N-1)

出力

答えとなる長さkのLISについて、k個の整数を1行のスペース区切りで出力してください。

B_0 B_1 .. B_(k-2) B_(k-1)

入力例1

6
4 5 6 1 2 3

出力例1

1 2 3

LISの長さは3であり、4 5 6と1 2 3が考えられます。辞書順最小の1 2 3を答えます。

入力例2

6
1 2 6 9 5 10

出力例2

1 2 6 9 10

LISがただ一つの場合は、それを出力してください。

入力例3

6
1 2 2 3 3 3

出力例3

1 2 3

広義増加(以上)ではなく、狭義増加(厳密に増加)であることに注意してください。

入力例4

1
100

出力例4

100