시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1041 139 74 14.149%

문제

정수로 이루어진 두 수열이 있다. 두 수열의 공통 증가 부분 수열 중 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.

길이가 N인 수열 S1, S2, ..., Sn이 길이가 M인 수열 A1, A2, ..., AM의 증가하는 부분 수열이 되려면, 모든 1 ≤ j ≤ N에 대해서, Sj = Aij인 1 ≤ i1 < i2 < ... < iN ≤ M가 존재하고, 모든 1 ≤ j < N에 대해 Sj < Sj+1을 만족해야 한다.

입력

두 수열의 정보는 각각 두 줄에 걸쳐서 주어지며, 첫째 줄에는 수열의 길이 M이 주어진다. (1 ≤ M ≤ 500) 다음 줄에는 M개의 정수 Ai (-231 ≤ Ai < 231)가 주어진다.

출력

첫째 줄에 최대 공통 증가 부분 수열의 길이를 출력하고, 둘째 줄에 그 부분 수열을 출력한다. 답이 여러가지인 경우에는 아무거나 출력한다.

예제 입력

5
1 4 2 5 -12
4
-12 1 2 4

예제 출력

2
1 4

힌트