← 返回题目列表

Codeforces · 1585/B

B. 数组翻转

中文机器翻译题面 查看原题

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

让我们定义外翻操作。让$$$x = a_n$$$。然后数组 $$$a$$$ 被分为两部分:左部分和右部分。左侧部分包含 $$$a$$$ 中不大于 $$$x$$$ ($$$\le x$$$) 的元素。右侧部分包含 $$$a$$$ 中严格大于 $$$x$$$ 的元素 ($$$> x$$$)。每个部分中元素的顺序保持与操作之前相同,即。 e.分区稳定。然后将数组替换为左右部分的串联。

例如,如果数组 $$$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$$$ 翻转后停止变化。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,打印一个整数 $$$k$$$ — 数组停止更改之前的翻转次数。

示例

输入 #1

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

输出 #1

1
2
0

注意

考虑第一个例子。

- 第一个版本:$$$a = [1, 4, 2, 5, 3]$$$,$$$x = 3$$$。 $$$[2, 4, 1, 5, 3] \ 到 [2, 1, 3], [4, 5] \ 到 [2, 1, 3, 4, 5]$$$。
- 第二个及后续版本:$$$a = [2, 1, 3, 4, 5]$$$,$$$x = 5$$$。 $$$[2, 1, 3, 4, 5] \ 到 [2, 1, 3, 4, 5], [] \ 到 [2, 1, 3, 4, 5]$$$。此版本不会更改数组,因此答案是 $$$1$$$。

考虑第二个例子。

- 第一个版本:$$$a = [5, 3, 2, 4, 1]$$$,$$$x = 1$$$。 $$$[5, 3, 2, 4, 1] \ 到 [1], [5, 3, 2, 4] \ 到 [1, 5, 3, 2, 4]$$$。
- 第二个版本:$$$a = [1, 5, 3, 2, 4]$$$,$$$x = 4$$$。 $$$[1, 5, 3, 2, 4] \ 到 [1, 3, 2, 4], [5] \ 到 [1, 3, 2, 4, 5]$$$。
- 第三个及以下版本:$$$a = [1, 3, 2, 4, 5]$$$,$$$x = 5$$$。 $$$[1, 3, 2, 4, 5] \ 到 [1, 3, 2, 4, 5], [] \ 到 [1, 3, 2, 4, 5]$$$。此版本不会更改数组,因此答案是 $$$2$$$。