시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1525 248 117 14.717%

문제

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

길이가 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+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1YWNmNVx1ZDFiNSBcdWM5OWRcdWFjMDAgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWRmOCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzQ3NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdyZWF0ZXN0IENvbW1vbiBJbmNyZWFzaW5nIFN1YnNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIHR3byBzZXF1ZW5jZXMgb2YgaW50ZWdlciBudW1iZXJzLiBXcml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoZWlyIGNvbW1vbiBpbmNyZWFzaW5nIHN1YnNlcXVlbmNlIG9mIG1heGltYWwgcG9zc2libGUgbGVuZ3RoLjxcL3A+XHJcblxyXG48cD5TZXF1ZW5jZSBTPHN1Yj4xPFwvc3ViPiwgUzxzdWI+MjxcL3N1Yj4sIC4uLiwgUzxzdWI+bjxcL3N1Yj4gb2YgbGVuZ3RoIE4gaXMgY2FsbGVkIGFuIGluY3JlYXNpbmcgc3Vic2VxdWVuY2Ugb2YgYSBzZXF1ZW5jZSBBPHN1Yj4xPFwvc3ViPiwgQTxzdWI+MjxcL3N1Yj4sIC4uLiwgQTxzdWI+TTxcL3N1Yj4gb2YgbGVuZ3RoIE0gaWYgdGhlcmUgZXhpc3QgMSAmbGU7IGk8c3ViPjE8XC9zdWI+Jm5ic3A7Jmx0OyBpPHN1Yj4yPFwvc3ViPiZuYnNwOyZsdDsgLi4uICZsdDsgaTxzdWI+TjxcL3N1Yj4gc3VjaCB0aGF0ICZuYnNwO1M8c3ViPmo8XC9zdWI+Jm5ic3A7PSBBPHN1Yj5pPHN1Yj5qPFwvc3ViPjxcL3N1Yj4gZm9yIGFsbCAxICZsZTsgaiAmbGU7IE4sIGFuZCBTPHN1Yj5qPFwvc3ViPiZuYnNwOyZsdDsgUzxzdWI+aisxPFwvc3ViPiBmb3IgYWxsIDEgJmxlOyBqJmx0O04uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHNlcXVlbmNlIGlzIGRlc2NyaWJlZCB3aXRoIE0gJm1kYXNoOyBpdHMgbGVuZ3RoICgxICZsZTsgTSAmbGU7IDUwMCkgYW5kIE0gaW50ZWdlciBudW1iZXJzJm5ic3A7QTxzdWI+aTxcL3N1Yj4mbmJzcDsoLTI8c3VwPjMxPFwvc3VwPiZuYnNwOyZsZTsgQTxzdWI+aTxcL3N1Yj4mbmJzcDsmbHQ7IDI8c3VwPjMxPFwvc3VwPikgJm1kYXNoOyB0aGUgc2VxdWVuY2UgaXRzZWxmLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgb3V0cHV0IFx1ZmIwMWxlIHByaW50IEwgJm1kYXNoOyB0aGUgbGVuZ3RoIG9mIHRoZSBncmVhdGVzdCBjb21tb24gaW5jcmVhc2luZyBzdWJzZXF1ZW5jZSBvZiBib3RoIHNlcXVlbmNlcy4gT24gdGhlIHNlY29uZCBsaW5lIHByaW50IHRoZSBzdWJzZXF1ZW5jZSBpdHNlbGYuIElmIHRoZXJlIGFyZSBzZXZlcmFsIHBvc3NpYmxlIGFuc3dlcnMsIG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=