Description

给定一个整数序列$A_1A_2A_3….A_n$。求它的一个递增子序列，使子序列的元素个数尽量多，元素不一定要求连续。

Format

Input

第1行：1个整数n(1<=n<=5000)，表示序列中元素的个数.

第2行-n+1行：每行1个整数x(-1000<=x<=1000)，第i+1行表示序列中的第i个元素。

Output

第1行：1个整数k，表示最长上升子序列的长度。

第2行：k个用单个空格分开的整数，表示找到了最长上升子序列。如果有多个长度等于k的子序列，则输出最靠前的1个。

Samples

8
1
3
2
4
3
5
4
6

5
1 3 4 5 6

Limitation

1s, 1024KiB for each test case.