P16760 [GKS 2020 #D] Alien Piano

一个外星人刚刚登陆地球，并且非常喜欢我们的音乐。算我们幸运。 外星人想把它最喜欢的人类歌曲带回家，但它只有一种非常奇怪的乐器：一架只有 $4$ 个不同音高的琴键的钢琴。 外星人通过将歌曲写成外星钢琴上的一系列琴键来转换歌曲。显然，这架钢琴无法完全转换我们的歌曲，因为我们的歌曲往往有远多于 $4$ 个音高。 外星人将改用以下规则来转换我们的歌曲： - 我们歌曲中的第一个音符可以转换为外星钢琴上的任意琴键。 - 对于之后的每个音符： - 如果它的音高高于前一个音符，则应转换为比前一个音符的转换结果更高音高的琴键； - 如果更低，则应转换为比前一个音符的转换结果更低音高的琴键； - 如果完全相同，则应转换为与前一个音符转换结果相同的琴键。 注意：两个相同音高的音符如果不相邻，则不需要转换为相同的琴键。 外星人想知道的是：在转换一首特定的歌曲时，它必须打破自己的规则的次数是多少？ 详细说明：让我们将一首歌曲描述为有 $K$ 个音符。第一个音符称为“音符 1”，第二个音符称为“音符 2”，最后一个音符称为“音符 $K$”。因此，音符 2 紧接在音符 1 之后。如果在我们版本的歌曲中，音符 2 的音高低于音符 1，但在外星人版本的歌曲中，它被转换为一个音高相等或更低的琴键（相对于音符 2 的转换），那么我们认为这是一次规则破坏。对于每个测试用例，返回外星人在转换该歌曲时必须打破其规则的最少次数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由两行组成。第一行包含一个整数 $K$。第二行包含 $K$ 个空格分隔的整数 $A_1, A_2, \dots, A_K$，其中 $A_i$ 表示该测试用例中第 $i$ 个音符的音高。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是该特定测试用例在外星人转换过程中必须打破其规则的最少次数。

我们将使用 A、B、C、D 表示外星钢琴的琴键，其中 A 是最低音，D 是最高音。在样例 #1 中，外星人可以简单地将我们的歌曲映射为以下序列：A B C D C，这正确地反映了以下所有关系： - 我们的第一个音符（音高 1）映射到 A， - 我们的第二个音符（音高 5）映射到它的琴键 B。5 > 1，且 B 是比 A 更高的琴键， - 我们的第三个音符（音高 100）映射到它的琴键 C。100 > 5，且 C 是比 B 更高的琴键， - 我们的第四个音符（音高 500）映射到它的琴键 D。500 > 100，且 D 是比 C 更高的琴键， - 我们的第五个音符（音高 1）映射到它的琴键 C。1 < 500，且 C 是比 D 更低的琴键。 因此没有规则被破坏。注意：A B C D C 不是唯一的转换方式。A B C D A 或 A B C D B 也是可行的转换。 在样例 #2 中，唯一能达到最少 1 次规则破坏的转换序列是：A B C D A B C D。值得注意的是，规则破坏来自这样一个事实：我们的第 4 个音符（音高 4）低于第 5 个音符（音高 5），但 A 是比 D 更低的琴键。 ### 限制条件 $1 \le T \le 100$。 $2 \le K \le 10^5$。 $1 \le A_i \le 10^9$。 **测试集 1** $K \le 10$。 **测试集 2** $K \le 10^5$。 翻译由 DeepSeek V4 Pro 完成