← 返回题目列表

Codeforces · 2204/B

B. 右最大

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

给定一个由 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 将执行的操作数。

示例

输入
复制

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

输出
复制

3
6
1
3

注意

在第一个示例中,数组为 $$$[2, 1, 2, 3, 1]$$$。对其进行以下操作:

  • 首先,选择第 $$$4$$$ 个元素。最后两个元素被移除,数组变为$$$[2, 1, 2]$$$;
  • 然后,选择$$$3$$$-rd 元素。最后一个元素被移除,数组变为$$$[2, 1]$$$;
  • 然后,选择$$$1$$$-st 元素。两个元素都被删除,因此在 $$$3$$$ 操作后数组变为空。