#P2079. 画矩形的qinhang3

画矩形的qinhang3

qinhang3 一小特别喜欢画画,最崇拜达芬奇。因为爱屋及乌,他每天都画矩形,而且只画矩形。他千虑一失,矩形没有鸡蛋那么千变万化,qinhang3终究还是qinhang3,落入GDUTACM集训队,成为计算几何神牛级人物。今天,qinhang3重温童年,又来画矩形了。<o:p></o:p>

他在ii+1上画一个高为h[i]的矩形,他画完之后把所有的矩形都涂上了同一种颜色。<o:p></o:p>

      现在给你一张 qinhang3的画画,已知ii+1上有一个高为h[i]的矩形,问 你最少画多少个矩形可以完成那幅画。<o:p></o:p>

Input

第一行 有T组数据;
每组数据 :第一行有一个正整数N;(0<N<=1000000)
第二行有N个自然数:h[1], h[2]. . h[N];(0<=h[i]<=10000)

Output

最少矩形个数,换行;

Sample Input

1
4
1 1 2 3

Sample Output

3

HINT

Source