가장 긴 증가하는 부분 수열 복원

수열 $A$가 주어지면 가장 긴 증가하는 부분 수열을 하나 찾는 프로그램을 작성한다. 부분 수열은 원소를 몇 개 골라 원래 순서를 유지한 채 이어 붙인 수열이고, 증가한다는 것은 앞의 원소가 뒤의 원소보다 항상 작다는 뜻이다. 값이 같은 원소는 두 개를 함께 고를 수 없다.

예를 들어 $A = \{10, 20, 10, 30, 20, 50\}$이면 10, 20, 30, 50이 길이 4인 증가하는 부분 수열이고, 이보다 긴 것은 없다.

길이가 최대인 증가하는 부분 수열이 여러 개일 수 있으므로, 그중 사전순으로 가장 작은 하나를 답으로 정한다. 길이가 같은 두 수열은 앞에서부터 값을 차례로 비교해, 처음으로 값이 달라지는 자리에서 더 작은 값을 가진 쪽이 사전순으로 앞선다.

첫째 줄에 수열 $A$의 크기 $N$이 주어진다. ($1 \le N \le 10^6$)

둘째 줄에 $A$를 이루는 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($-10^9 \le A_i \le 10^9$)

첫째 줄에 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에 길이가 최대인 증가하는 부분 수열 중 사전순으로 가장 작은 것을 공백으로 구분해 출력한다.