일련의 수가 주어질 때 이 수들을 앞에서 부터 차례대로 선택하는 문제이다. 단 앞에서 선택한 수보다 뒤에서 선택한 수가 무조건 더 커야된다.

* 이러한 문제를 최대부분증가수열(LIS)라고 한다.

입력

• 데이터의 개수를 나타내는 (1 <= N <= 500,000)이 주어지고
• 다음 줄에는 N개의 데이터가 주어진다. 데이터는 32 비트 정수범위 내로 주어진다.

출력

• 첫 줄에는 최대 부분 증가수열의 개수와
• 다음 줄에는 최대부분증가수열을 출력한다.

입출력 예

입력

5
1 4 6 4 2

출력

3
1 4 6

출처:makesource
special judge:makesource