最長増加部分列を見つける

n 個の整数からなる配列が与えられたとき、その配列における最長の増加部分列を求めてください。もし最長増加部分列が複数ある場合は、そのいずれかを出力してもかまいません。

配列の部分列とは、元の配列からいくつかの要素（0個でも可）を削除し、残った要素の順序を変えずに並べたものを指します。たとえば、配列が の場合、 は の部分列です。しかし、 は、要素の順序が保たれていないため部分列とはみなされません。

Input

入力の最初の行には、配列の長さを示す単一の整数 n (1 ≤ n ≤ 100000) が与えられます。

2行目には、配列の要素を表す () がスペース区切りで与えられます。

Output

出力の最初の行には、配列の最長増加部分列の長さを表す整数 k を出力してください。

続く2行目には、最長増加部分列を構成する k 個の整数をスペース区切りで出力してください。

Examples

Note

2番目の例では、 も長さ 3 の正しい増加部分列として有効です。