長さの数列の最長増加部分列 (LIS: Longest Increasing Subsequence) のうち、辞書順最小であるものを出力してください。

数列のLISとは、で、を満たすうち、が最も大きいものです。 (つまり、狭義増加のLISです)

辞書順最小とは、の長さのLISであるがあるとき、全ての()に対して、が成り立つとき、は数列の辞書順最小であるLISといいます。

制約


入力


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

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 61 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

Submit


Go (1.14)