当前没有测试数据。

C. 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 \leq t \leq 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
3
4

提示

第一个测试用例的操作流程：

1. 在第 5 个按钮（权重 5）前创建一个克隆体。
2. 在第 1 个按钮（权重 4）前创建一个克隆体。
3. 将第二个克隆体从第 1 个按钮移动到第 2 个（权重 3）。
4. 将第二个克隆体从第 2 个按钮移动到第 3 个（权重 2）。
5. 将第一个克隆体从第 5 个按钮移动到第 4 个（权重 1）。

按下顺序为 $5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1$，满足非递增要求。可以证明这是所需克隆体数量最少的方案。

第二个测试用例的操作流程：

1. 在第 2 个按钮（权重 1）前创建一个克隆体。
2. 将该克隆体从第 2 个按钮移动到第 3 个（权重 1）。
3. 将该克隆体从第 3 个按钮移动到第 2 个（已按下，无操作）。
4. 将该克隆体从第 2 个按钮移动到第 1 个（权重 1）。

按下顺序为 $1 \rightarrow 1 \rightarrow 1$，满足要求。