← 返回题目列表

Codeforces · 2108/C

C. 尼奥的逃亡

中文机器翻译题面 查看原题

尼奥想要逃离黑客帝国。在他面前是排成一排的 $$$n$$$ 按钮。每个按钮都有一个由整数给出的权重:$$$a_1、a_2、\ldots、a_n$$$。

尼奥无法动弹,但他可以创建和移动克隆体。这意味着他可以以任意顺序执行无限数量的以下两种类型的操作:

  1. 在特定按钮前面创建一个克隆。
  2. 将现有克隆向左或向右移动一位。

一旦克隆体位于另一个尚未按下的按钮前面 - 无论他是被创建还是移动 - 他 立即 按下它。如果按钮已经被按下,则克隆不会执行任何操作 - 按钮只能按下一次。

为了让尼奥逃脱,他需要按 全部 按钮的顺序如下: 非增加 — 也就是说,如果 $$$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$$$。

输出

对于每个测试用例,输出一个整数——按有效顺序按下所有按钮所需创建的最小克隆数。

示例

输入
复制

4
5
4 3 2 1 5
3
1 1 1
6
7 8 1 5 9 2
10
1 7 9 7 1 10 2 10 10 7

输出
复制

2
1
2
3

注意

在第一个测试用例中,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$$$。