Description

煎饼通常以堆叠的形式供应，但无限煎饼屋勇于变革！该餐厅的新广告噱头是将煎饼以双端队列（deque）的形式供应。

你是餐厅的服务员，你的工作是从双端队列中供应所有煎饼。顾客会依次到来，每位顾客获得一个煎饼。你必须为每位顾客供应当前双端队列的最左端或最右端的煎饼，选择权在你手中。当一个煎饼被供应后，它会从队列中消失，露出相邻的煎饼。或者，当只剩一个煎饼时，你只能供应它，此时你的工作就完成了！

每个煎饼有一个美味值。由于顾客无法选择自己获得的煎饼，只有当一个煎饼的美味值不低于之前所有顾客获得的煎饼的美味值时，该顾客才需要为其煎饼付费。（第一位顾客总是需要付费，因为此时没有之前的顾客。）

如果你以最大化付费顾客数量的顺序供应煎饼，有多少顾客会为其煎饼付费？

Input Format

输入的第一行包含测试用例的数量 $T$。随后是 $T$ 个测试用例。每个测试用例由两行描述：第一行包含一个整数 $N$，表示双端队列中煎饼的数量；第二行包含 $N$ 个整数 $D_1, D_2, \ldots, D_N$，其中 $D_i$ 表示队列中从左数第 $i$ 个煎饼的美味值。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是以最大化付费顾客数量的顺序供应煎饼时的付费顾客数。

4
2
1 5
4
1 4 2 3
5
10 10 10 10 10
4
7 1 3 1000000

Case #1: 2
Case #2: 3
Case #3: 5
Case #4: 2

Hint

样例解释

在样例 #1 中，有两种供应煎饼的顺序。如果先供应美味值为 5 的煎饼，则只有该顾客付费；如果先供应美味值为 1 的煎饼，则两位顾客都会付费。

样例 #2 对应题目描述中的图片。以下是可能的供应顺序（按美味值），下划线的煎饼表示顾客需要付费：

• $\underline{1}, 4, 2, 3$
• $\underline{1}, 4, 3, 2$
• $\underline{1}, \underline{3}, 4, 2$
• $\underline{1}, \underline{3}, 2, \underline{4}$
• $\underline{3}, 1, \underline{4}, 2$
• $\underline{3}, 1, 2, \underline{4}$
• $\underline{3}, 2, 1, \underline{4}$
• $\underline{3}, 2, \underline{4}, 1$

可以看到，某些顺序下会有 3 个煎饼被付费，但没有一种顺序能让所有 4 个煎饼都付费。

在样例 #3 中，无论以何种顺序供应，所有煎饼都会被付费。

在样例 #4 中，无论先供应哪个煎饼，中间的两个煎饼都不会被付费。最佳策略是先供应美味值为 7 的煎饼，再供应美味值为 1000000 的煎饼。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq D_i \leq 10^6$（对所有 $i$ 成立）。

测试集 1（7 分，可见判定）

• $2 \leq N \leq 20$。

测试集 2（8 分，可见判定）

• $2 \leq N \leq 100$。

测试集 3（10 分，隐藏判定）

• $2 \leq N \leq 10^5$。

翻译由 DeepSeek V3 完成