9075번 - Missile Protector 다국어채점 준비 중

Think about a nation named X that is in war with its neighboring country. Mr. Y, an army officer, is in charge of protecting the main bordering area of that country. He has managed to get information that the neighboring country is planning for some missile attack. A secret agent of the neighboring country has been caught by the army of X while spying. But before being caught he destroyed the main control center of missile protector. The alternative way to control the missile protector is to control it manually.

Missile protector is a device to destroy missiles that operates at a fixed height at a particular time. Normally it is electronically controlled and can set its height automatically by detecting the incoming missiles. But since it is now manually operated it’s no more so efficient. It takes longer time to change the current position. Particularly it’s more time consuming to set into the appropriate height when the new height is less than the current height.

Mr. Z, the main secret agent of X has got very important information and that is the arrival time of the missile and their height. Unfortunately the arrival time is such that height of the protector can only be increased during the attack of any two consecutive missiles. So Mr. Y has decided only to increase the height of the missile protector if necessary but never decrease. Definitely this strategy can protect all the missiles only if they are in non-decreasing height as compared to the previously coming missiles. But the strategy here is to destroy as many missiles as possible.

Mr. Y is requesting your help to write a program that will take the sequence of missile height according to their arrival time and your program should output the maximum number of missile that can be protected with the strategy described above. You can assume that the initial height of the missile protector is zero.

The input consists of T (1
T
20) test cases. The first line of the input file contains an integer representing the number of test cases. Each test case begins with a line containing a positive integer N (
500), indicating the number of missiles attacking in this case. The following line represents the heights of the missiles according to their arrival time numbered 1, 2,…, N. The height values are nonnegative integers less than 500 separated by a single space.

Print exactly one line for each test case in the output. The line should contain the maximum number of missiles that can be blocked by the missile protector.