A16520. Right Maximum
编程题
普及-
知识点
题目描述
给定一个包含 $n$ 个整数的数组 $a$。
每当数组非空时，执行如下操作：
- 首先选出数组中的最大元素（如果有多个最大元素，选择最右边的那个）；
- 然后移除该元素及其之后的所有元素（包含该元素本身）。
你的任务是计算，在数组变空前，将会执行多少次这样的操作。
每当数组非空时，执行如下操作：
- 首先选出数组中的最大元素（如果有多个最大元素，选择最右边的那个）；
- 然后移除该元素及其之后的所有元素（包含该元素本身）。
你的任务是计算，在数组变空前，将会执行多少次这样的操作。
输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例包含两行：
- 第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）；
- 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
输入的附加限制：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
每个测试用例包含两行：
- 第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）；
- 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
输入的附加限制：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，输出一行一个整数，表示将要执行的操作次数。
输入输出样例
输入 #1
4 5 2 1 2 3 1 6 1 2 3 4 5 6 3 3 2 1 4 1 3 3 1
输出 #1
3 6 1 3
说明/提示
在第一个示例中，数组为 $[2, 1, 2, 3, 1]$。按以下顺序执行操作：
- 首先选择第 $4$ 个元素。最后两个元素被移除，数组变为 $[2, 1, 2]$；
- 然后选择第 $3$ 个元素。最后一个元素被移除，数组变为 $[2, 1]$；
- 然后选择第 $1$ 个元素。两个元素都被移除，操作共执行 $3$ 次，数组变为空。
- 首先选择第 $4$ 个元素。最后两个元素被移除，数组变为 $[2, 1, 2]$；
- 然后选择第 $3$ 个元素。最后一个元素被移除，数组变为 $[2, 1]$；
- 然后选择第 $1$ 个元素。两个元素都被移除，操作共执行 $3$ 次，数组变为空。