P12987 [GCJ 2022 #1B] Pancake Deque

煎饼通常以堆叠的形式供应，但**无限煎饼屋**勇于变革！该餐厅的新广告噱头是将煎饼以双端队列（deque）的形式供应。 你是餐厅的服务员，你的工作是从双端队列中供应所有煎饼。顾客会依次到来，每位顾客获得一个煎饼。你必须为每位顾客供应当前双端队列的最左端或最右端的煎饼，选择权在你手中。当一个煎饼被供应后，它会从队列中消失，露出相邻的煎饼。或者，当只剩一个煎饼时，你只能供应它，此时你的工作就完成了！  每个煎饼有一个美味值。由于顾客无法选择自己获得的煎饼，只有当一个煎饼的美味值**不低于**之前所有顾客获得的煎饼的美味值时，该顾客才需要为其煎饼付费。（第一位顾客总是需要付费，因为此时没有之前的顾客。） 如果你以最大化付费顾客数量的顺序供应煎饼，有多少顾客会为其煎饼付费？

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

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

**样例解释** 在样例 #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 完成