CF1437D.Minimal Height Tree

Monocarp had a tree which consisted of $n$ vertices and was rooted at vertex $1$. He decided to study BFS (Breadth-first search), so he ran BFS on his tree, starting from the root. BFS can be described by the following pseudocode:

a = [] # the order in which vertices were processedq = Queue()q.put(1) # place the root at the end of the queuewhile not q.empty():    k = q.pop() # retrieve the first vertex from the queue    a.append(k) # append k to the end of the sequence in which vertices were visited    for y in g[k]: # g[k] is the list of all children of vertex k, sorted in ascending order        q.put(y)

Monocarp was fascinated by BFS so much that, in the end, he lost his tree. Fortunately, he still has a sequence of vertices, in which order vertices were visited by the BFS algorithm (the array a from the pseudocode). Monocarp knows that each vertex was visited exactly once (since they were put and taken from the queue exactly once). Also, he knows that all children of each vertex were viewed in ascending order.

Monocarp knows that there are many trees (in the general case) with the same visiting order $a$, so he doesn't hope to restore his tree. Monocarp is okay with any tree that has minimum height.

The height of a tree is the maximum depth of the tree's vertices, and the depth of a vertex is the number of edges in the path from the root to it. For example, the depth of vertex $1$ is $0$, since it's the root, and the depth of all root's children are $1$.

Help Monocarp to find any tree with given visiting order $a$ and minimum height.

Monocarp 原本有一棵由 $n$ 个顶点构成的树，根节点为顶点 $1$。他决定研究 BFS（广度优先搜索），于是从根节点开始在该树上运行 BFS。BFS 可用如下伪代码描述：

a = [] # 顶点被处理的顺序
q = Queue()
q.put(1) # 将根节点加入队列尾部
while not q.empty():
    k = q.pop() # 从队列头部取出第一个顶点
    a.append(k) # 将 k 追加到顶点访问顺序序列 a 的末尾
    for y in g[k]: # g[k] 是顶点 k 的所有子节点列表，按升序排列
        q.put(y)

Monocarp 对 BFS 如此着迷，以至于最后竟丢失了自己的树。幸运的是，他仍保留了 BFS 算法访问顶点的顺序（即伪代码中的数组 a）。Monocarp 知道每个顶点恰好被访问一次（因为每个顶点恰好入队和出队一次）。此外，他还知道：对每个顶点，其所有子节点均按升序被遍历。

Monocarp 意识到，一般情况下，存在许多棵不同的树能产生相同的 BFS 访问序列 $a$，因此他并不指望能唯一还原出原来的树。只要能得到任意一棵满足给定访问序列 $a$ 且高度最小的树，他就满意了。

树的高度定义为树中所有顶点深度的最大值；而一个顶点的深度定义为从根节点到该顶点的路径所含边的数量。例如，顶点 $1$ 的深度为 $0$（因其为根节点），而根节点的所有子节点的深度均为 $1$。

请帮助 Monocarp 找到一棵满足给定访问序列 $a$ 且高度最小的树。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$; $a_i \neq a_j$; $a_1 = 1$) — the order in which the vertices were visited by the BFS algorithm.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 树中顶点的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$；当 $i \neq j$ 时，$a_i \neq a_j$；且 $a_1 = 1$）—— BFS 算法访问顶点的顺序。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case print the minimum possible height of a tree with the given visiting order $a$.

对于每个测试用例，输出满足给定访问顺序 $a$ 的树的最小可能高度。

In the first test case, there is only one tree with the given visiting order:

In the second test case, there is only one tree with the given visiting order as well:

In the third test case, an optimal tree with the given visiting order is shown below:

在第一个测试用例中，仅存在一棵满足给定遍历顺序的树：

在第二个测试用例中，同样仅存在一棵满足给定遍历顺序的树：

在第三个测试用例中，一棵满足给定遍历顺序的最优树如下所示：