시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 170 34 27 48.214%

문제

온 나라가 고통받았던 전쟁이 끝났습니다. 전쟁을 교훈삼아, 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+XHVjNzc0XHVkNmM0IFx1YjQ1MCBcdWM5MDRcdWM1MjkgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjY2FiXHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWQwYzBcdWM2Y2NcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG4gJmxlOyAyICZtaWRkb3Q7IDEwPHN1cD41PFwvc3VwPiBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxiciBcLz5cclxuXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAxMDxzdXA+OTxcL3N1cD4gXHVjNzc0XHVkNTU4XHVjNzc4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1YWMxY1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjNWYwXHVjMThkXHVkNTVjIFx1ZDBjMFx1YzZjY1x1Yjk3YyBcdWM1YzZcdWM1NjBcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWM1ZjBcdWMxOGRcdWQ1NWMgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1ZDBjMFx1YzZjY1x1YjRlNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM0MjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEZWZlbnNlIExpbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5BZnRlciB0aGUgbGFzdCB3YXIgZGV2YXN0YXRlZCB5b3VyIGNvdW50cnksIHlvdSAmbWRhc2g7IGFzIHRoZSBraW5nIG9mIHRoZSBsYW5kIG9mIEFyZGVuaWEgJm1kYXNoOyBkZWNpZGVkIGl0IHdhcyBoaWdoIHRpbWUgdG8gaW1wcm92ZSB0aGUgZGVmZW5zZSBvZiB5b3VyIGNhcGl0YWwgY2l0eS4gQSBwYXJ0IG9mIHlvdXIgZm9ydGlmaWNhdGlvbiBpcyBhIGxpbmUgb2YgbWFnZSB0b3dlcnMsIHN0YXJ0aW5nIG5lYXIgdGhlIGNpdHkgYW5kIGNvbnRpbnVpbmcgdG8gdGhlIG5vcnRoZXJuIHdvb2RzLiBZb3VyIGFkdmlzb3JzIGRldGVybWluZWQgdGhhdCB0aGUgcXVhbGl0eSBvZiB0aGUgZGVmZW5zZSBkZXBlbmRlZCBvbmx5IG9uIG9uZSBmYWN0b3I6IHRoZSBsZW5ndGggb2YgYSBsb25nZXN0IGNvbnRpZ3VvdXMgdG93ZXIgc2VxdWVuY2Ugb2YgaW5jcmVhc2luZyBoZWlnaHRzLiAoVGhleSBnYXZlIHlvdSBhIGxlbmd0aHkgZXhwbGFuYXRpb24sIGJ1dCB0aGUgb25seSB0aGluZyB5b3UgdW5kZXJzdG9vZCB3YXMgdGhhdCBpdCBoYWQgc29tZXRoaW5nIHRvIGRvIHdpdGggZmlyaW5nIGVuZXJneSBib2x0cyBhdCBlbmVteSBmb3JjZXMpLjxcL3A+XHJcblxyXG48cD5BZnRlciBzb21lIGhhcmQgbmVnb3RpYXRpb25zLCBpdCBhcHBlYXJlZCB0aGF0IGJ1aWxkaW5nIG5ldyB0b3dlcnMgaXMgb3V0IG9mIHRoZSBxdWVzdGlvbi4gTWFnZXMgb2YgQXJkZW5pYSBoYXZlIGFncmVlZCB0byBkZW1vbGlzaCBzb21lIG9mIHRoZWlyIHRvd2VycywgdGhvdWdoLiBZb3UgbWF5IGRlbW9saXNoIGFyYml0cmFyeSBudW1iZXIgb2YgdG93ZXJzLCBidXQgdGhlIG1hZ2VzIGVuZm9yY2VkIG9uZSBjb25kaXRpb246IHRoZXNlIHRvd2VycyBoYXZlIHRvIGJlIGNvbnNlY3V0aXZlLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlIGhlaWdodHMgb2YgdG93ZXJzIHdlcmUsIHJlc3BlY3RpdmVseSwgNSwgMywgNCwgOSwgMiwgOCwgNiwgNywgMSwgdGhlbiBieSBkZW1vbGlzaGluZyB0b3dlcnMgb2YgaGVpZ2h0cyA5LCAyLCBhbmQgOCwgdGhlIGxvbmdlc3QgaW5jcmVhc2luZyBzZXF1ZW5jZSBvZiBjb25zZWN1dGl2ZSB0b3dlcnMgaXMgMywgNCwgNiwgNy48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBaICZsZTsgMjUsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlbiBaIHRlc3QgY2FzZXMgZm9sbG93LCBlYWNoIGNvbmZvcm1pbmcgdG8gdGhlIGZvcm1hdCBkZXNjcmliZWQgaW4gc2VjdGlvbiBJbnB1dC4gRm9yIGVhY2ggdGVzdCBjYXNlLCB5b3VyIHByb2dyYW0gaGFzIHRvIHdyaXRlIGFuIG91dHB1dCBjb25mb3JtaW5nIHRvIHRoZSBmb3JtYXQgZGVzY3JpYmVkIGluIHNlY3Rpb24gT3V0cHV0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGluc3RhbmNlIGNvbnNpc3RzIG9mIHR3byBsaW5lcy4gVGhlIGZpcnN0IG9uZSBjb250YWlucyBvbmUgcG9zaXRpdmUgaW50ZWdlciBuICZsZTsgMiAmbWlkZG90OyAxMDxzdXA+NTxcL3N1cD4gZGVub3RpbmcgdGhlIG51bWJlciBvZiB0b3dlcnMuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIHBvc2l0aXZlIGludGVnZXJzIG5vdCBsYXJnZXIgdGhhbiAxMDkgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgYmVpbmcgdGhlIGhlaWdodHMgb2YgdGhlIHRvd2Vycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3Ugc2hvdWxkIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBsZW5ndGggb2YgYSBsb25nZXN0IGluY3JlYXNpbmcgc2VxdWVuY2Ugb2YgY29uc2VjdXRpdmUgdG93ZXJzLCBhY2hpZXZhYmxlIGJ5IGRlbW9saXNoaW5nIHNvbWUgY29uc2VjdXRpdmUgdG93ZXJzIG9yIG5vIHRvd2VyIGF0IGFsbC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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