시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB5041168429.893%

문제

온 나라가 고통받았던 전쟁이 끝났습니다. 전쟁을 교훈삼아, Ardenia의 수도의 방어선을 탄탄하게 할 때가 되었습니다. 방어선 중 가장 핵심적인 부분은 수도에서 북쪽 숲으로 뻗어나가는 메이지 타워입니다. 메이지 타워에서 Ardenia를 지키는 마법사들은 Ardenia의 왕인 당신에게 방어에 대한 한 가지 조언을 하였습니다. 적군에게 에너지 볼트를 쓰는 것에 관한 긴 설명을 하긴 했지만, 결국 당신이 이해하기로는 도시의 방어의 질은 높이가 증가하는 순서대로의 연속된 타워들 중 가장 길이가 긴 것에 의해 결정된다는 것입니다.

새로운 타워를 짓는 것은 불가능한 것으로 보이고, 일단은 몇 개의 타워를 없애서 도시의 방어의 질을 높이려고 합니다. (타워를 없애지 않아도 됩니다.) 타워를 없애는 일이 복잡하기 때문에, 마법사들이 한 가지 조건을 걸었습니다: 없애는 타워들은 연속해야 합니다.

예를 들어, 타워들의 높이가 5, 3, 4, 9, 2, 8, 6, 7, 1 이었다고 합시다. 밑줄 친 (연속한) 타워들을 없애면, 높이가 5, 3, 4, 6, 7, 1인 타워들이 남고, 여기서 가장 긴 연속한 증가하는 부분은 굵게 표시한 3, 4, 6, 7이 됩니다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있습니다.

첫째 줄에는 테스트 케이스의 개수 Z ≤ 25 가 주어집니다.

이후 두 줄씩 입력이 주어지는데, 첫째 줄은 타워의 수를 나타내는 양의 정수 n ≤ 2 · 105 이 주어집니다. 둘째 줄에는 109 이하인 양의 정수 n개가 공백으로 구분되어 주어집니다.

출력

각각의 테스트 케이스에 대해, 몇 개의 연속한 타워를 없애서 만들 수 있는 가장 긴 연속한 증가하는 타워들의 길이를 출력하세요.

예제 입력 1

2
9
5 3 4 9 2 8 6 7 1
7
1 2 3 10 4 5 6

예제 출력 1

4
6
W3sicHJvYmxlbV9pZCI6IjM0MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMjlcdWM1YjRcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyOCBcdWIwOThcdWI3N2NcdWFjMDAgXHVhY2UwXHVkMWI1XHViYzFiXHVjNTU4XHViMzU4IFx1YzgwNFx1YzdjMVx1Yzc3NCBcdWIwNWRcdWIwYWNcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YzgwNFx1YzdjMVx1Yzc0NCBcdWFkNTBcdWQ2YzhcdWMwYmNcdWM1NDQsIEFyZGVuaWFcdWM3NTggXHVjMjE4XHViM2M0XHVjNzU4IFx1YmMyOVx1YzViNFx1YzEyMFx1Yzc0NCBcdWQwYzRcdWQwYzRcdWQ1NThcdWFjOGMgXHVkNTYwIFx1YjU0Y1x1YWMwMCBcdWI0MThcdWM1YzhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YmMyOVx1YzViNFx1YzEyMCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDU3NVx1YzJlY1x1YzgwMVx1Yzc3OCBcdWJkODBcdWJkODRcdWM3NDAgXHVjMjE4XHViM2M0XHVjNWQwXHVjMTFjIFx1YmQ4MVx1Y2FiZCBcdWMyMzJcdWM3M2NcdWI4NWMgXHViZWQ3XHVjNWI0XHViMDk4XHVhYzAwXHViMjk0IFx1YmE1NFx1Yzc3NFx1YzljMCBcdWQwYzBcdWM2Y2NcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YmE1NFx1Yzc3NFx1YzljMCBcdWQwYzBcdWM2Y2NcdWM1ZDBcdWMxMWMgQXJkZW5pYVx1Yjk3YyBcdWM5YzBcdWQwYTRcdWIyOTQgXHViOWM4XHViYzk1XHVjMGFjXHViNGU0XHVjNzQwIEFyZGVuaWFcdWM3NTggXHVjNjU1XHVjNzc4IFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4YyBcdWJjMjlcdWM1YjRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVjODcwXHVjNWI4XHVjNzQ0IFx1ZDU1OFx1YzYwMFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjODAxXHVhZDcwXHVjNWQwXHVhYzhjIFx1YzVkMFx1YjEwOFx1YzljMCBcdWJjZmNcdWQyYjhcdWI5N2MgXHVjNGYwXHViMjk0IFx1YWM4M1x1YzVkMCBcdWFkMDBcdWQ1NWMgXHVhZTM0IFx1YzEyNFx1YmE4NVx1Yzc0NCBcdWQ1NThcdWFlMzQgXHVkNTg4XHVjOWMwXHViOWNjLCBcdWFjYjBcdWFkNmQgXHViMmY5XHVjMmUwXHVjNzc0IFx1Yzc3NFx1ZDU3NFx1ZDU1OFx1YWUzMFx1Yjg1Y1x1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzI5XHVjNWI0XHVjNzU4IFx1YzljOFx1Yzc0MCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVkMGMwXHVjNmNjXHViNGU0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWUzNCBcdWFjODNcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YWNiMFx1YzgxNVx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQwYzBcdWM2Y2NcdWI5N2MgXHVjOWQzXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhYzgzXHVjNzNjXHViODVjIFx1YmNmNFx1Yzc3NFx1YWNlMCwgXHVjNzdjXHViMmU4XHVjNzQwIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkMGMwXHVjNmNjXHViOTdjIFx1YzVjNlx1YzU2MFx1YzExYyBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzI5XHVjNWI0XHVjNzU4IFx1YzljOFx1Yzc0NCBcdWIxOTJcdWM3NzRcdWI4MjRcdWFjZTAgXHVkNTY5XHViMmM4XHViMmU0LiAoXHVkMGMwXHVjNmNjXHViOTdjIFx1YzVjNlx1YzU2MFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDI5XHViMmM4XHViMmU0LikgXHVkMGMwXHVjNmNjXHViOTdjIFx1YzVjNlx1YzU2MFx1YjI5NCBcdWM3N2NcdWM3NzQgXHViY2Y1XHVjN2ExXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViOWM4XHViYzk1XHVjMGFjXHViNGU0XHVjNzc0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YWM3OFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNDogXHVjNWM2XHVjNTYwXHViMjk0IFx1ZDBjMFx1YzZjY1x1YjRlNFx1Yzc0MCBcdWM1ZjBcdWMxOGRcdWQ1NzRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwYzBcdWM2Y2NcdWI0ZTRcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwJm5ic3A7NSwgMywgNCwgPHU+OSwgMiwgODxcL3U+LCA2LCA3LCAxIFx1Yzc3NFx1YzVjOFx1YjJlNFx1YWNlMCBcdWQ1NjlcdWMyZGNcdWIyZTQuIFx1YmMxMVx1YzkwNCBcdWNlNWMgKFx1YzVmMFx1YzE4ZFx1ZDU1YykgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YmE3NCwgXHViMTkyXHVjNzc0XHVhYzAwIDUsIDxzdHJvbmc+MywgNCwgNiwgNzxcL3N0cm9uZz4sIDFcdWM3NzggXHVkMGMwXHVjNmNjXHViNGU0XHVjNzc0IFx1YjBhOFx1YWNlMCwgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNWYwXHVjMThkXHVkNTVjIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NDAgXHVhZDc1XHVhYzhjIFx1ZDQ1Y1x1YzJkY1x1ZDU1YyAzLCA0LCA2LCA3XHVjNzc0IFx1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBaICZsZTsgMjUgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFx1YjQ1MCBcdWM5MDRcdWM1MjkgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjY2FiXHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWQwYzBcdWM2Y2NcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG4gJmxlOyAyICZtaWRkb3Q7IDEwPHN1cD41PFwvc3VwPiBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IDEwPHN1cD45PFwvc3VwPiBcdWM3NzRcdWQ1NThcdWM3NzggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVhYzFjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWQ1NWMgXHVkMGMwXHVjNmNjXHViOTdjIFx1YzVjNlx1YzU2MFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzVmMFx1YzE4ZFx1ZDU1YyBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzQyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRlZmVuc2UgTGluZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIHRoZSBsYXN0IHdhciBkZXZhc3RhdGVkIHlvdXIgY291bnRyeSwgeW91ICZtZGFzaDsgYXMgdGhlIGtpbmcgb2YgdGhlIGxhbmQgb2YgQXJkZW5pYSAmbWRhc2g7IGRlY2lkZWQgaXQgd2FzIGhpZ2ggdGltZSB0byBpbXByb3ZlIHRoZSBkZWZlbnNlIG9mIHlvdXIgY2FwaXRhbCBjaXR5LiBBIHBhcnQgb2YgeW91ciBmb3J0aWZpY2F0aW9uIGlzIGEgbGluZSBvZiBtYWdlIHRvd2Vycywgc3RhcnRpbmcgbmVhciB0aGUgY2l0eSBhbmQgY29udGludWluZyB0byB0aGUgbm9ydGhlcm4gd29vZHMuIFlvdXIgYWR2aXNvcnMgZGV0ZXJtaW5lZCB0aGF0IHRoZSBxdWFsaXR5IG9mIHRoZSBkZWZlbnNlIGRlcGVuZGVkIG9ubHkgb24gb25lIGZhY3RvcjogdGhlIGxlbmd0aCBvZiBhIGxvbmdlc3QgY29udGlndW91cyB0b3dlciBzZXF1ZW5jZSBvZiBpbmNyZWFzaW5nIGhlaWdodHMuIChUaGV5IGdhdmUgeW91IGEgbGVuZ3RoeSBleHBsYW5hdGlvbiwgYnV0IHRoZSBvbmx5IHRoaW5nIHlvdSB1bmRlcnN0b29kIHdhcyB0aGF0IGl0IGhhZCBzb21ldGhpbmcgdG8gZG8gd2l0aCBmaXJpbmcgZW5lcmd5IGJvbHRzIGF0IGVuZW15IGZvcmNlcykuPFwvcD5cclxuXHJcbjxwPkFmdGVyIHNvbWUgaGFyZCBuZWdvdGlhdGlvbnMsIGl0IGFwcGVhcmVkIHRoYXQgYnVpbGRpbmcgbmV3IHRvd2VycyBpcyBvdXQgb2YgdGhlIHF1ZXN0aW9uLiBNYWdlcyBvZiBBcmRlbmlhIGhhdmUgYWdyZWVkIHRvIGRlbW9saXNoIHNvbWUgb2YgdGhlaXIgdG93ZXJzLCB0aG91Z2guIFlvdSBtYXkgZGVtb2xpc2ggYXJiaXRyYXJ5IG51bWJlciBvZiB0b3dlcnMsIGJ1dCB0aGUgbWFnZXMgZW5mb3JjZWQgb25lIGNvbmRpdGlvbjogdGhlc2UgdG93ZXJzIGhhdmUgdG8gYmUgY29uc2VjdXRpdmUuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgaGVpZ2h0cyBvZiB0b3dlcnMgd2VyZSwgcmVzcGVjdGl2ZWx5LCA1LCAzLCA0LCA5LCAyLCA4LCA2LCA3LCAxLCB0aGVuIGJ5IGRlbW9saXNoaW5nIHRvd2VycyBvZiBoZWlnaHRzIDksIDIsIGFuZCA4LCB0aGUgbG9uZ2VzdCBpbmNyZWFzaW5nIHNlcXVlbmNlIG9mIGNvbnNlY3V0aXZlIHRvd2VycyBpcyAzLCA0LCA2LCA3LjxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIFogJmxlOyAyNSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGVuIFogdGVzdCBjYXNlcyBmb2xsb3csIGVhY2ggY29uZm9ybWluZyB0byB0aGUgZm9ybWF0IGRlc2NyaWJlZCBpbiBzZWN0aW9uIElucHV0LiBGb3IgZWFjaCB0ZXN0IGNhc2UsIHlvdXIgcHJvZ3JhbSBoYXMgdG8gd3JpdGUgYW4gb3V0cHV0IGNvbmZvcm1pbmcgdG8gdGhlIGZvcm1hdCBkZXNjcmliZWQgaW4gc2VjdGlvbiBPdXRwdXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaW5zdGFuY2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgZmlyc3Qgb25lIGNvbnRhaW5zIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIG4gJmxlOyAyICZtaWRkb3Q7IDEwPHN1cD41PFwvc3VwPiBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHRvd2Vycy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG4gcG9zaXRpdmUgaW50ZWdlcnMgbm90IGxhcmdlciB0aGFuIDEwPHN1cD45PFwvc3VwPiBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyBiZWluZyB0aGUgaGVpZ2h0cyBvZiB0aGUgdG93ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBzaG91bGQgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGxlbmd0aCBvZiBhIGxvbmdlc3QgaW5jcmVhc2luZyBzZXF1ZW5jZSBvZiBjb25zZWN1dGl2ZSB0b3dlcnMsIGFjaGlldmFibGUgYnkgZGVtb2xpc2hpbmcgc29tZSBjb25zZWN1dGl2ZSB0b3dlcnMgb3Igbm8gdG93ZXIgYXQgYWxsLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Central European Regional Contest > CERC 2010 D번

  • 문제의 오타를 찾은 사람: h0ngjun7
  • 어색한 표현을 찾은 사람: jh05013
  • 문제를 번역한 사람: namnamseo