最長増加部分列を見つける
n 個の整数からなる配列が与えられたとき、その配列における最長の増加部分列を求めてください。もし最長増加部分列が複数ある場合は、そのいずれかを出力してもかまいません。配列の部分列とは、元の配列からいくつかの要素（0個でも可）を削除し、残った要素の順序を変えずに並べたものを指します。たとえば、配列が の場合、 は の部分列です。しかし、 は、要素の順序が保たれていないため部分列とはみなされません。
💡
配列の増加部分列とは、要素が昇順になるよう並んでいる部分列を指します。たとえば、配列が の場合、 は の増加部分列ですが、 は要素が昇順になっていないため、増加部分列ではありません。
Input
入力の最初の行には、配列の長さを示す単一の整数
n (1 ≤ n ≤ 100000) が与えられます。2行目には、配列の要素を表す () がスペース区切りで与えられます。
Output
出力の最初の行には、配列の最長増加部分列の長さを表す整数
k を出力してください。続く2行目には、最長増加部分列を構成する
k 個の整数をスペース区切りで出力してください。Examples
入力 | 出力 |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Note
2番目の例では、 も長さ 3 の正しい増加部分列として有効です。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB