시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 550 | 139 | 98 | 31.410% |
온 나라가 고통받았던 전쟁이 끝났습니다. 전쟁을 교훈삼아, 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개가 공백으로 구분되어 주어집니다.
각각의 테스트 케이스에 대해, 몇 개의 연속한 타워를 없애서 만들 수 있는 가장 긴 연속한 증가하는 타워들의 길이를 출력하세요.
2 9 5 3 4 9 2 8 6 7 1 7 1 2 3 10 4 5 6
4 6