Description

Scott 有一个蚂蚁农场，里面有 $N$ 只蚂蚁。每只蚂蚁都有一定的体长和体重。

今天，Scott 给蚂蚁们设置了一个挑战：他把一些食物放在蚂蚁农场的顶部。蚂蚁们会尝试通过把自己叠成一根竖直的“蚂蚁塔”来够到食物，每只蚂蚁都直接背着下一只蚂蚁。这样，每只蚂蚁都要承受其上方所有蚂蚁的重量。Scott 的蚂蚁们非常强壮，每只蚂蚁最多可以承受自身重量的 6 倍。例如，一只重 8 毫克的蚂蚁可以承受两只各重 24 毫克的蚂蚁！每只蚂蚁也有一个体长；具体长度不重要，只要它们的长度都不相同即可。

• 蚂蚁塔必须是线性的。除了最顶上的蚂蚁外，每只蚂蚁正上方必须有且只有一只蚂蚁；除了最底下的蚂蚁外，每只蚂蚁正下方必须有且只有一只蚂蚁。
• 蚂蚁塔中蚂蚁的体长必须从下到上严格递减；这保证了每只新加入蚂蚁都能顺利爬到顶部。
• 对于塔中的每只蚂蚁，其上方所有蚂蚁的总重量不得超过该蚂蚁自身重量的 6 倍。

请问最多能有多少只蚂蚁组成这样一根蚂蚁塔？

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据的第一行为一个整数 $N$，表示蚂蚁的数量。第二行为 $N$ 个整数 $W_1, W_2, ..., W_N$，其中 $W_i$ 表示第 $i$ 只蚂蚁的重量（单位：毫克）。蚂蚁按照体长严格递增的顺序给出。注意，实际长度值未给出，只需关心顺序。

Output Format

对于每组测试数据，输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示最多能组成的蚂蚁塔的蚂蚁数量。

3
2
9 1
3
8 4 100
9
10 10 10 10 10 10 10 10 100

Case #1: 1
Case #2: 3
Case #3: 8

Hint

样例解释

在样例 1 中，有两只蚂蚁。第一只重 9 毫克，第二只重 1 毫克，且第二只比第一只体长更长。第一只蚂蚁足够强壮，可以承受第二只蚂蚁（因为它能承受 $9 \times 6$ 毫克），但由于第二只蚂蚁体长更长，不能叠在第一只上。第二只蚂蚁无法承受第一只蚂蚁（因为它只能承受 $1 \times 6$ 毫克，小于 9 毫克）。所以只能单独选其中一只蚂蚁组成“蚂蚁塔”。

在样例 2 中，三只蚂蚁可以全部组成一根蚂蚁塔，第三只承受第二只，第二只承受第一只。

在样例 3 中，最优解是第九只蚂蚁在最底下，其上方再叠七只其它蚂蚁。

数据范围

• $7 \leqslant T \leqslant 100$。

测试点 1（16 分，可见）

• 恰有 6 组数据 $N = 100$；其余 $T-6$ 组 $2 \leqslant N \leqslant 50$。
• $1 \leqslant W_i \leqslant 1000$，对所有 $i$。

测试点 2（27 分，隐藏）

• 恰有 6 组数据 $N = 10^5$；其余 $T-6$ 组 $2 \leqslant N \leqslant 500$。
• $1 \leqslant W_i \leqslant 10^9$，对所有 $i$。

由 ChatGPT 4.1 翻译