尼奥想要逃离黑客帝国。在他面前是排成一排的 $$$n$$$ 按钮。每个按钮都有一个由整数给出的权重:$$$a_1、a_2、\ldots、a_n$$$。
尼奥无法动弹,但他可以创建和移动克隆体。这意味着他可以以任意顺序执行无限数量的以下两种类型的操作:
- 在特定按钮前面创建一个克隆。
- 将现有克隆向左或向右移动一位。
一旦克隆体位于另一个尚未按下的按钮前面 - 无论他是被创建还是移动 - 他 立即 按下它。如果按钮已经被按下,则克隆不会执行任何操作 - 按钮只能按下一次。
为了让尼奥逃脱,他需要按 全部 按钮的顺序如下: 非增加 — 也就是说,如果 $$$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$$$。
输出
对于每个测试用例,输出一个整数——按有效顺序按下所有按钮所需创建的最小克隆数。
示例
输入复制
454 3 2 1 531 1 167 8 1 5 9 2101 7 9 7 1 10 2 10 10 7
输出复制
2 1 2 3
注意
在第一个测试用例中,Neo 可以执行以下操作:
- 在第五个按钮前面创建一个克隆(重量为 $$$5$$$)。
- 在第一个按钮前面创建一个克隆(权重为 $$$4$$$)。
- 将第二个克隆从第一个按钮移动到第二个按钮(权重为 $$$3$$$)。
- 将第二个克隆从第二个按钮移动到第三个按钮(权重为 $$$2$$$)。
- 将第一个克隆从第五个按钮移动到第四个按钮(权重为 $$$1$$$)。
在第二个测试用例中,Neo 可以执行以下操作:
- 在第二个按钮前面创建一个克隆(权重为 $$$1$$$)。
- 将克隆从第二个按钮移动到第三个按钮(重量为 $$$1$$$)。
- 将克隆从第三个按钮移动到第二个按钮(已按下)。
- 将克隆从第二个按钮移动到第一个按钮(权重为 $$$1$$$)。