시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 97 24 21 53.846%

문제

온 나라가 고통받았던 전쟁이 끝났습니다. 전쟁을 교훈삼아, 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
W3sicHJvYmxlbV9pZCI6IjM0MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMjlcdWM1YjRcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyOCBcdWIwOThcdWI3N2NcdWFjMDAgXHVhY2UwXHVkMWI1XHViYzFiXHVjNTU4XHViMzU4IFx1YzgwNFx1YzdjMVx1Yzc3NCBcdWIwNWRcdWIwYWNcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YzgwNFx1YzdjMVx1Yzc0NCBcdWFkNTBcdWQ2YzhcdWMwYmNcdWM1NDQsIEFyZGVuaWFcdWM3NTggXHVjMjE4XHViM2M0XHVjNzU4IFx1YmMyOVx1YzViNFx1YzEyMFx1Yzc0NCBcdWQwYzRcdWQwYzRcdWQ1NThcdWFjOGMgXHVkNTYwIFx1YjU0Y1x1YWMwMCBcdWI0MThcdWM1YzhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YmMyOVx1YzViNFx1YzEyMCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDU3NVx1YzJlY1x1YzgwMVx1Yzc3OCBcdWJkODBcdWJkODRcdWM3NDAgXHVjMjE4XHViM2M0XHVjNWQwXHVjMTFjIFx1YmQ4MVx1Y2FiZCBcdWMyMzJcdWM3M2NcdWI4NWMgXHViZWQ3XHVjNWI0XHViMDk4XHVhYzAwXHViMjk0IFx1YmE1NFx1Yzc3NFx1YzljMCBcdWQwYzBcdWM2Y2NcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YmE1NFx1Yzc3NFx1YzljMCBcdWQwYzBcdWM2Y2NcdWM1ZDBcdWMxMWMgQXJkZW5pYVx1Yjk3YyBcdWM5YzBcdWQwYTRcdWIyOTQgXHViOWM4XHViYzk1XHVjMGFjXHViNGU0XHVjNzQwIEFyZGVuaWFcdWM3NTggXHVjNjU1XHVjNzc4IFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4YyBcdWJjMjlcdWM1YjRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVjODcwXHVjNWI4XHVjNzQ0IFx1ZDU1OFx1YzYwMFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjODAxXHVhZDcwXHVjNWQwXHVhYzhjIFx1YzVkMFx1YjEwOFx1YzljMCBcdWJjZmNcdWQyYjhcdWI5N2MgXHVjNGYwXHViMjk0IFx1YWM4M1x1YzVkMCBcdWFkMDBcdWQ1NWMgXHVhZTM0IFx1YzEyNFx1YmE4NVx1Yzc0NCBcdWQ1NThcdWFlMzQgXHVkNTg4XHVjOWMwXHViOWNjLCBcdWFjYjBcdWFkNmQgXHViMmY5XHVjMmUwXHVjNzc0IFx1Yzc3NFx1ZDU3NFx1ZDU1OFx1YWUzMFx1Yjg1Y1x1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzI5XHVjNWI0XHVjNzU4IFx1YzljOFx1Yzc0MCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVkMGMwXHVjNmNjXHViNGU0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWUzNCBcdWFjODNcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YWNiMFx1YzgxNVx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjA5OFx1YzkxMVx1YzVkMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVkMGMwXHVjNmNjXHViOTdjIFx1YzlkM1x1YWNhMFx1YzljMFx1YjljYywgXHVjNzdjXHViMmU4XHVjNzQwIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkMGMwXHVjNmNjXHViOTdjIFx1YzVjNlx1YzU2MFx1YzExYyBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzI5XHVjNWI0XHVjNzU4IFx1YzljOFx1Yzc0NCBcdWIxOTJcdWM3NzRcdWI4MjRcdWFjZTAgXHVkNTY5XHViMmM4XHViMmU0LiAoXHVkMGMwXHVjNmNjXHViOTdjIFx1YzVjNlx1YzU2MFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDI5XHViMmM4XHViMmU0LikgXHVkMGMwXHVjNmNjXHViOTdjIFx1YzVjNlx1YzU2MFx1YjI5NCBcdWM3N2NcdWM3NzQgXHViY2Y1XHVjN2ExXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViOWM4XHViYzk1XHVjMGFjXHViNGU0XHVjNzc0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YWM3OFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNDogXHVjNWM2XHVjNTYwXHViMjk0IFx1ZDBjMFx1YzZjY1x1YjRlNFx1Yzc0MCBcdWM1ZjBcdWMxOGRcdWQ1NzRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwYzBcdWM2Y2NcdWI0ZTRcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwJm5ic3A7NSwgMywgNCwgPHU+OSwgMiwgODxcL3U+LCA2LCA3LCAxIFx1Yzc3NFx1YzVjOFx1YjJlNFx1YWNlMCBcdWQ1NjlcdWMyZGNcdWIyZTQuIFx1YmMxMVx1YzkwNCBcdWNlNWMgKFx1YzVmMFx1YzE4ZFx1ZDU1YykgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YmE3NCwgXHViMTkyXHVjNzc0XHVhYzAwIDUsIDxzdHJvbmc+MywgNCwgNiwgNzxcL3N0cm9uZz4sIDFcdWM3NzggXHVkMGMwXHVjNmNjXHViNGU0XHVjNzc0IFx1YjBhOFx1YWNlMCwgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNWYwXHVjMThkXHVkNTVjIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NDAgXHVhZDc1XHVhYzhjIFx1ZDQ1Y1x1YzJkY1x1ZDU1YyAzLCA0LCA2LCA3XHVjNzc0IFx1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBaICZsZTsgMjUgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFx1YjQ1MCBcdWM5MDRcdWM1MjkgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjY2FiXHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWQwYzBcdWM2Y2NcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG4gJmxlOyAyICZtaWRkb3Q7IDEwPHN1cD41PFwvc3VwPiBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxiciBcLz5cclxuXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAxMDxzdXA+OTxcL3N1cD4gXHVjNzc0XHVkNTU4XHVjNzc4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1YWMxY1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjNWYwXHVjMThkXHVkNTVjIFx1ZDBjMFx1YzZjY1x1Yjk3YyBcdWM1YzZcdWM1NjBcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWM1ZjBcdWMxOGRcdWQ1NWMgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1ZDBjMFx1YzZjY1x1YjRlNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM0MjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEZWZlbnNlIExpbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5BZnRlciB0aGUgbGFzdCB3YXIgZGV2YXN0YXRlZCB5b3VyIGNvdW50cnksIHlvdSAmbWRhc2g7IGFzIHRoZSBraW5nIG9mIHRoZSBsYW5kIG9mIEFyZGVuaWEgJm1kYXNoOyBkZWNpZGVkIGl0IHdhcyBoaWdoIHRpbWUgdG8gaW1wcm92ZSB0aGUgZGVmZW5zZSBvZiB5b3VyIGNhcGl0YWwgY2l0eS4gQSBwYXJ0IG9mIHlvdXIgZm9ydGlmaWNhdGlvbiBpcyBhIGxpbmUgb2YgbWFnZSB0b3dlcnMsIHN0YXJ0aW5nIG5lYXIgdGhlIGNpdHkgYW5kIGNvbnRpbnVpbmcgdG8gdGhlIG5vcnRoZXJuIHdvb2RzLiBZb3VyIGFkdmlzb3JzIGRldGVybWluZWQgdGhhdCB0aGUgcXVhbGl0eSBvZiB0aGUgZGVmZW5zZSBkZXBlbmRlZCBvbmx5IG9uIG9uZSBmYWN0b3I6IHRoZSBsZW5ndGggb2YgYSBsb25nZXN0IGNvbnRpZ3VvdXMgdG93ZXIgc2VxdWVuY2Ugb2YgaW5jcmVhc2luZyBoZWlnaHRzLiAoVGhleSBnYXZlIHlvdSBhIGxlbmd0aHkgZXhwbGFuYXRpb24sIGJ1dCB0aGUgb25seSB0aGluZyB5b3UgdW5kZXJzdG9vZCB3YXMgdGhhdCBpdCBoYWQgc29tZXRoaW5nIHRvIGRvIHdpdGggZmlyaW5nIGVuZXJneSBib2x0cyBhdCBlbmVteSBmb3JjZXMpLjxcL3A+XHJcblxyXG48cD5BZnRlciBzb21lIGhhcmQgbmVnb3RpYXRpb25zLCBpdCBhcHBlYXJlZCB0aGF0IGJ1aWxkaW5nIG5ldyB0b3dlcnMgaXMgb3V0IG9mIHF1ZXN0aW9uLiBNYWdlcyBvZiBBcmRlbmlhIGhhdmUgYWdyZWVkIHRvIGRlbW9saXNoIHNvbWUgb2YgdGhlaXIgdG93ZXJzLCB0aG91Z2guIFlvdSBtYXkgZGVtb2xpc2ggYXJiaXRyYXJ5IG51bWJlciBvZiB0b3dlcnMsIGJ1dCB0aGUgbWFnZXMgZW5mb3JjZWQgb25lIGNvbmRpdGlvbjogdGhlc2UgdG93ZXJzIGhhdmUgdG8gYmUgY29uc2VjdXRpdmUuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgaGVpZ2h0cyBvZiB0b3dlcnMgd2VyZSwgcmVzcGVjdGl2ZWx5LCA1LCAzLCA0LCA5LCAyLCA4LCA2LCA3LCAxLCB0aGVuIGJ5IGRlbW9saXNoaW5nIHRvd2VycyBvZiBoZWlnaHRzIDksIDIsIGFuZCA4LCB0aGUgbG9uZ2VzdCBpbmNyZWFzaW5nIHNlcXVlbmNlIG9mIGNvbnNlY3V0aXZlIHRvd2VycyBpcyAzLCA0LCA2LCA3LjxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIFogJmxlOyAyNSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGVuIFogdGVzdCBjYXNlcyBmb2xsb3csIGVhY2ggY29uZm9ybWluZyB0byB0aGUgZm9ybWF0IGRlc2NyaWJlZCBpbiBzZWN0aW9uIElucHV0LiBGb3IgZWFjaCB0ZXN0IGNhc2UsIHlvdXIgcHJvZ3JhbSBoYXMgdG8gd3JpdGUgYW4gb3V0cHV0IGNvbmZvcm1pbmcgdG8gdGhlIGZvcm1hdCBkZXNjcmliZWQgaW4gc2VjdGlvbiBPdXRwdXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaW5zdGFuY2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgZmlyc3Qgb25lIGNvbnRhaW5zIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIG4gJmxlOyAyICZtaWRkb3Q7IDEwPHN1cD41PFwvc3VwPiBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHRvd2Vycy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG4gcG9zaXRpdmUgaW50ZWdlcnMgbm90IGxhcmdlciB0aGFuIDEwOSBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyBiZWluZyB0aGUgaGVpZ2h0cyBvZiB0aGUgdG93ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBzaG91bGQgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGxlbmd0aCBvZiBhIGxvbmdlc3QgaW5jcmVhc2luZyBzZXF1ZW5jZSBvZiBjb25zZWN1dGl2ZSB0b3dlcnMsIGFjaGlldmFibGUgYnkgZGVtb2xpc2hpbmcgc29tZSBjb25zZWN1dGl2ZSB0b3dlcnMgb3Igbm8gdG93ZXIgYXQgYWxsLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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