시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1455 207 115 14.706%

문제

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

길이가 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)가 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

2
1 4
W3sicHJvYmxlbV9pZCI6Ijc0NzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDAgXHVhY2Y1XHVkMWI1IFx1Yzk5ZFx1YWMwMCBcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhY2Y1XHVkMWI1IFx1Yzk5ZFx1YWMwMCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWM4M1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc4IFx1YzIxOFx1YzVmNCBTPHN1Yj4xPFwvc3ViPiwgUzxzdWI+MjxcL3N1Yj4sIC4uLiwgUzxzdWI+bjxcL3N1Yj5cdWM3NzQgXHVhZTM4XHVjNzc0XHVhYzAwIE1cdWM3NzggXHVjMjE4XHVjNWY0IEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5NPFwvc3ViPlx1Yzc1OCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWI0MThcdWI4MjRcdWJhNzQsIFx1YmFhOFx1YjRlMCAxICZsZTsgaiAmbGU7IE5cdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBTPHN1Yj5qPFwvc3ViPiA9IEE8c3ViPmk8c3ViPmo8XC9zdWI+PFwvc3ViPlx1Yzc3OCAxICZsZTsgaTxzdWI+MTxcL3N1Yj4gJmx0OyBpPHN1Yj4yPFwvc3ViPiAmbHQ7IC4uLiAmbHQ7IGk8c3ViPk48XC9zdWI+ICZsZTsgTVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWFjZTAsIFx1YmFhOFx1YjRlMCAxICZsZTsgaiAmbHQ7IE5cdWM1ZDAgXHViMzAwXHVkNTc0IFM8c3ViPmo8XC9zdWI+ICZsdDsgUzxzdWI+aisxPFwvc3ViPlx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YjQ1MCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE0gJmxlOyA1MDApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggQTxzdWI+aTxcL3N1Yj4gKC0yPHN1cD4zMTxcL3N1cD4gJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbHQ7IDI8c3VwPjMxPFwvc3VwPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1YWNmNVx1ZDFiNSBcdWM5OWRcdWFjMDAgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWRmOCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NDc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3JlYXRlc3QgQ29tbW9uIEluY3JlYXNpbmcgU3Vic2VxdWVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gdHdvIHNlcXVlbmNlcyBvZiBpbnRlZ2VyIG51bWJlcnMuIFdyaXRlIGEgcHJvZ3JhbSB0byBkZXRlcm1pbmUgdGhlaXIgY29tbW9uIGluY3JlYXNpbmcgc3Vic2VxdWVuY2Ugb2YgbWF4aW1hbCBwb3NzaWJsZSBsZW5ndGguPFwvcD5cclxuXHJcbjxwPlNlcXVlbmNlIFM8c3ViPjE8XC9zdWI+LCBTPHN1Yj4yPFwvc3ViPiwgLi4uLCBTPHN1Yj5uPFwvc3ViPiBvZiBsZW5ndGggTiBpcyBjYWxsZWQgYW4gaW5jcmVhc2luZyBzdWJzZXF1ZW5jZSBvZiBhIHNlcXVlbmNlIEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5NPFwvc3ViPiBvZiBsZW5ndGggTSBpZiB0aGVyZSBleGlzdCAxICZsZTsgaTxzdWI+MTxcL3N1Yj4mbmJzcDsmbHQ7IGk8c3ViPjI8XC9zdWI+Jm5ic3A7Jmx0OyAuLi4gJmx0OyBpPHN1Yj5OPFwvc3ViPiBzdWNoIHRoYXQgJm5ic3A7UzxzdWI+ajxcL3N1Yj4mbmJzcDs9IEE8c3ViPmk8c3ViPmo8XC9zdWI+PFwvc3ViPiBmb3IgYWxsIDEgJmxlOyBqICZsZTsgTiwgYW5kIFM8c3ViPmo8XC9zdWI+Jm5ic3A7Jmx0OyBTPHN1Yj5qKzE8XC9zdWI+IGZvciBhbGwgMSAmbGU7IGombHQ7Ti48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggc2VxdWVuY2UgaXMgZGVzY3JpYmVkIHdpdGggTSAmbWRhc2g7IGl0cyBsZW5ndGggKDEgJmxlOyBNICZsZTsgNTAwKSBhbmQgTSBpbnRlZ2VyIG51bWJlcnMmbmJzcDtBPHN1Yj5pPFwvc3ViPiZuYnNwOygtMjxzdXA+MzE8XC9zdXA+Jm5ic3A7JmxlOyBBPHN1Yj5pPFwvc3ViPiZuYnNwOyZsdDsgMjxzdXA+MzE8XC9zdXA+KSAmbWRhc2g7IHRoZSBzZXF1ZW5jZSBpdHNlbGYuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBvdXRwdXQgXHVmYjAxbGUgcHJpbnQgTCAmbWRhc2g7IHRoZSBsZW5ndGggb2YgdGhlIGdyZWF0ZXN0IGNvbW1vbiBpbmNyZWFzaW5nIHN1YnNlcXVlbmNlIG9mIGJvdGggc2VxdWVuY2VzLiBPbiB0aGUgc2Vjb25kIGxpbmUgcHJpbnQgdGhlIHN1YnNlcXVlbmNlIGl0c2VsZi4gSWYgdGhlcmUgYXJlIHNldmVyYWwgcG9zc2libGUgYW5zd2Vycywgb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==