가장 긴 증가하는 부분 수열 4

수열 $A$가 주어진다. $A$에서 원소를 몇 개 골라 원래 순서를 유지한 채 이어 붙인 수열을 $A$의 부분 수열이라고 하고, 그 부분 수열의 값이 앞에서 뒤로 갈수록 항상 커지면 증가하는 부분 수열이라고 한다.

$A$의 증가하는 부분 수열 중 길이가 가장 긴 것을 찾아 길이와 원소를 출력하는 프로그램을 작성하시오.

예를 들어 $A = \{10, 20, 10, 30, 20, 50\}$이면 가장 긴 증가하는 부분 수열은 첫째, 둘째, 넷째, 여섯째 원소를 고른 $\{10, 20, 30, 50\}$이고 길이는 $4$이다.

길이가 가장 긴 증가하는 부분 수열은 여러 개일 수 있다. 그런 경우에는 사전순으로 가장 앞서는 것 하나만 답으로 인정한다. 길이가 같은 두 수열은 앞에서부터 값을 차례로 비교해서 처음으로 다른 자리의 값이 더 작은 쪽이 사전순으로 앞선다.

첫째 줄에 수열 $A$의 길이 $N$이 주어진다. ($1 \le N \le 1{,}000$)

둘째 줄에 $A$의 원소 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 1{,}000$)

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

둘째 줄에 그 부분 수열의 원소를 앞에서부터 공백으로 구분해 출력한다. 길이가 가장 긴 증가하는 부분 수열이 여러 개면 그중 사전순으로 가장 앞서는 것을 출력한다.