CF1585B.Array Eversion

You are given an array $a$ of length $n$.

Let's define the eversion operation. Let $x = a_n$. Then array $a$ is partitioned into two parts: left and right. The left part contains the elements of $a$ that are not greater than $x$ ($\le x$). The right part contains the elements of $a$ that are strictly greater than $x$ ($ \gt x$). The order of elements in each part is kept the same as before the operation, i. e. the partition is stable. Then the array is replaced with the concatenation of the left and the right parts.

For example, if the array $a$ is $[2, 4, 1, 5, 3]$, the eversion goes like this: $[2, 4, 1, 5, 3] \to [2, 1, 3], [4, 5] \to [2, 1, 3, 4, 5]$.

We start with the array $a$ and perform eversions on this array. We can prove that after several eversions the array $a$ stops changing. Output the minimum number $k$ such that the array stops changing after $k$ eversions.

给你一个长度为 $n$ 的数组 $a$。

我们定义一种称为“翻转”（eversion）的操作。令 $x = a_n$。然后将数组 $a$ 划分为左右两部分：左部分包含所有不大于 $x$（即 $\le x$）的元素；右部分包含所有严格大于 $x$（即 $> x$）的元素。每部分中元素的相对顺序保持不变（即该划分是稳定的）。接着，用左部分与右部分的拼接结果替换原数组。

例如，若数组 $a$ 为 $[2, 4, 1, 5, 3]$，则翻转过程如下：
$[2, 4, 1, 5, 3] \to [2, 1, 3], [4, 5] \to [2, 1, 3, 4, 5]$。

我们从初始数组 $a$ 出发，反复执行翻转操作。可以证明：经过若干次翻转后，数组 $a$ 将不再发生变化。请输出最小的整数 $k$，使得经过 $k$ 次翻转后数组停止变化。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是测试用例的描述。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

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

For each test case print a single integer $k$ — the number of eversions after which the array stops changing.

对于每个测试用例，输出一个整数 $k$ —— 数组停止变化所需的翻转次数。

Consider the fist example.

• The first eversion: $a = [1, 4, 2, 5, 3]$, $x = 3$. $[2, 4, 1, 5, 3] \to [2, 1, 3], [4, 5] \to [2, 1, 3, 4, 5]$.
• The second and following eversions: $a = [2, 1, 3, 4, 5]$, $x = 5$. $[2, 1, 3, 4, 5] \to [2, 1, 3, 4, 5], [] \to [2, 1, 3, 4, 5]$. This eversion does not change the array, so the answer is $1$.

Consider the second example.

• The first eversion: $a = [5, 3, 2, 4, 1]$, $x = 1$. $[5, 3, 2, 4, 1] \to [1], [5, 3, 2, 4] \to [1, 5, 3, 2, 4]$.
• The second eversion: $a = [1, 5, 3, 2, 4]$, $x = 4$. $[1, 5, 3, 2, 4] \to [1, 3, 2, 4], [5] \to [1, 3, 2, 4, 5]$.
• The third and following eversions: $a = [1, 3, 2, 4, 5]$, $x = 5$. $[1, 3, 2, 4, 5] \to [1, 3, 2, 4, 5], [] \to [1, 3, 2, 4, 5]$. This eversion does not change the array, so the answer is $2$.

考虑第一个例子。

• 第一次翻转：$a = [1, 4, 2, 5, 3]$，$x = 3$。$[2, 4, 1, 5, 3] \to [2, 1, 3], [4, 5] \to [2, 1, 3, 4, 5]$。
• 第二次及之后的翻转：$a = [2, 1, 3, 4, 5]$，$x = 5$。$[2, 1, 3, 4, 5] \to [2, 1, 3, 4, 5], [] \to [2, 1, 3, 4, 5]$。此次翻转未改变数组，因此答案为 $1$。

考虑第二个例子。

• 第一次翻转：$a = [5, 3, 2, 4, 1]$，$x = 1$。$[5, 3, 2, 4, 1] \to [1], [5, 3, 2, 4] \to [1, 5, 3, 2, 4]$。
• 第二次翻转：$a = [1, 5, 3, 2, 4]$，$x = 4$。$[1, 5, 3, 2, 4] \to [1, 3, 2, 4], [5] \to [1, 3, 2, 4, 5]$。
• 第三次及之后的翻转：$a = [1, 3, 2, 4, 5]$，$x = 5$。$[1, 3, 2, 4, 5] \to [1, 3, 2, 4, 5], [] \to [1, 3, 2, 4, 5]$。此次翻转未改变数组，因此答案为 $2$。