#Î. A Famous City

    Type: Default 1000ms 256MiB

A Famous City

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

先生.B抵达华沙后,他被摩天大楼震惊了,拍了几张照片。但现在,当他看到这些照片时,他惊讶地发现,他甚至无法指出其中的建筑物数量。因此,他决定按如下方式进行处理:

  • 将照片从左到右分成n个垂直部分。照片中的建筑物可以被视为矩形,其下边缘是地平线。一个建筑物可以跨越几个连续的部分,但每个部分只能包含一个可见的建筑物,或者根本没有建筑物。
  • 测量该作品中每栋建筑的高度。
  • 编写一个程序来计算建筑物的最小数量。 先生.B已经完成了前两个步骤,最后一个步骤来到你身边。

Format

Input

T 组测试数据,每个测试用例都以一行开头,其中包含一个整数 n (1 <= n < = 100,000)。下面是一行包含 n 个整数 - 分别是每块建筑的高度。请注意,零高度意味着这件作品中根本没有建筑物。所有输入数字都将是非负数,并且小于 1,000,000,000。

Output

对于每个测试用例,在照片中显示一行,其中包含案例编号和最小可能数量的建筑物。

输出样例的图例

Samples

2
3
1 2 3
3
1 2 1
Case 1: 3
Case 2: 2

Hint

The possible configurations of the samples are illustrated below:

Limitation

1s, 1024KiB for each test case.

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45