Minimal Height Tree

## 题面 Monocarp有一颗以结点 $1$ 为根结点的树。他打算学习BFS（此处是能打开的OI Wiki，内有C++伪代码，原链接在上面的题面中[Breadth-first search](https://oi-wiki.org/graph/bfs/)），所以他对这颗树从根结点开始进行了BFS。BFS的伪代码如下（我就修一下题面 C++的伪代码去wiki看吧）： ``` a = [] # the order in which vrtices wre procssed # 结点被遍历的顺序 q = Queue() q.put(1) # place the root at the end of the queue # 把根结点放入队尾 while not q.empty(): k = q.pop() # retrieve the first vertex from the queue # 取出队首元素append a.append(k) # k to the end of sequence in which vertices were visited # 将k放入已被遍历的序列末尾 for y in g[k]: # g[k] is the list of all children of vertx k, sorted in ascedfing order # 意思是 ：g[k]存有 k 的全部子结点，且按升序排列 q.put(y) ``` Monocarp沉迷BFS无法自拔，最后把自己的树给搞丢了，只留下了一个BFS序列 $a$。Monocarp知道每个结点只被遍历一次（因为他们只入队和出队一次），并且知道每个结点的子结点是按升序遍历的。 Monocarp知道不同的树可能有相同的BFS序列，因此他不期待能够找回原来的树，他只想得到根据BFS序列能得到的高度最小的树。 树的高度是树中结点的最大深度。一个结点的深度为从根结点到达它的路径上的边的数量。比如，结点 $1$ 的深度是 $0$，因为它是根结点，所以他的所有子节点的深度都是 $1$。 请根据给出的 $a$ 序列帮助 Monocarp 找到高度最小的树。 ## 输入 第一行一个整数 $t\,(1\le t\le 1000)$，表示有 $t$ 组测试数据。 每一组测试数据的的一行有一个整数 $n(a\le n\le 2\,·\!10^5)$，表示树中结点个数。 每组测试数据的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n (1\le a_i \le n;a_i\ne a_j ;a_1=1)$。 所有测试数据中的 $n$ 的总和不超过 $2·\!10^5$。 ## 输出 每行一个整数，表示树的最小高度

Monocarp had a tree which consisted of $ n $ vertices and was rooted at vertex $ 1 $ . He decided to study BFS ([Breadth-first search](https://en.wikipedia.org/wiki/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 processed q = Queue() q.put(1) # place the root at the end of the queue while 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.

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 $ .

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

3
4
1 4 3 2
2
1 2
3
1 2 3

3
1
1

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: