文理学院程序设计在线练习


最少失误

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 49   Accepted Submission(s): 21
Problem Description

时代在改变,导弹拦截系统也有了变化。

某国为了防御敌国的导弹袭击,花重金从国外购置了2套导弹拦截系统。分别称作A系统和B系统。
A系统的特点是,第一发炮弹能够到达任意的高度,但是以后每一发炮弹都必须高于前一发的高度。
B系统的特点是,第一发炮弹能够到达任意的高度,但是以后每一发炮弹都必须低于前一发的高度。

某天,雷达捕捉到敌国的导弹来袭.请你进行最精密的安排,使得这2套系统能够拦截尽可能多的导弹。
注意: 这2套系统的使用顺序不限定,但是无法同时使用。也就是说,一旦开始使用第二套系统,则先使用的那套系统自动失效。

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。(1<=T<=30)
对于每组测试数据,第一行是正整数n (1<=n<=100), 表示导弹总个数,第二行有n个整数,表示导弹依次飞来的高度(其高度是不大于10000的正整数,中间用空格分隔)。

Output

对于每组测试,若能全部拦截,则输出0,否则请输出无法拦截的导弹总数(当然应该是越少越好)。

Sample Input
2
8 989 222 135 340 256 171 158 5
5 5 4 3 4 5
Sample Output
2
0
Hint

对于sample1,可以使用A系统拦截222,340, B系统拦截256,171,158,5. 剩下989和135无法拦截。
对于sample2,可以使用B系统拦截5,4,3, A系统拦截4,5。

Source

绍兴文理学院第五届程序设计竞赛2011/03/27