CF2108C Neo's Escape

Neo 想要逃离矩阵世界。在他面前有一排 $n$ 个按钮，每个按钮都有一个整数权重：$a_1, a_2, \ldots, a_n$。 Neo 被固定住了，但他可以创建和移动克隆体。这意味着他可以按任意顺序执行以下两种操作，次数不限： 1. 在特定按钮前创建一个克隆体。 2. 将现有的克隆体向左或向右移动一个位置。 当一个克隆体位于尚未被按下的按钮前时（无论他是被创建还是被移动的），他会立即按下该按钮。如果按钮已经被按下过，克隆体不会做任何操作——每个按钮只能被按下一次。 为了成功逃脱，Neo 需要以特定的顺序按下所有按钮：按钮权重的序列必须是非递增的。也就是说，如果 $b_1, b_2, \ldots, b_n$ 是按按钮的顺序对应的权重，那么必须满足 $b_1 \geq b_2 \geq \cdots \geq b_n$。 你的任务是确定 Neo 需要创建的最少克隆体数量，以便能够以有效顺序按下所有按钮。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——按钮的数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）——按钮的权重。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数——为了以有效顺序按下所有按钮需要创建的最少克隆体数量。

在第一个测试用例中，Neo 可以按以下方式操作： 1. 在第五个按钮（权重为 $5$）前创建一个克隆体。 2. 在第一个按钮（权重为 $4$）前创建第二个克隆体。 3. 将第二个克隆体从第一个按钮移动到第二个按钮（权重为 $3$）。 4. 将第二个克隆体从第二个按钮移动到第三个按钮（权重为 $2$）。 5. 将第一个克隆体从第五个按钮移动到第四个按钮（权重为 $1$）。 这样，按钮按下的顺序将是 $5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1$，满足要求。可以证明，创建的克隆体数量是最小的。 在第二个测试用例中，Neo 可以按以下方式操作： 1. 在第二个按钮（权重为 $1$）前创建一个克隆体。 2. 将该克隆体从第二个按钮移动到第三个按钮（权重为 $1$）。 3. 将该克隆体从第三个按钮移回第二个按钮（已被按下）。 4. 将该克隆体从第二个按钮移动到第一个按钮（权重为 $1$）。 这样，按钮按下的顺序将是 $1 \rightarrow 1 \rightarrow 1$。 翻译由 DeepSeek V3 完成