← 返回题目列表

Codeforces · 2210/B

B. 简单地坐在椅子上

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

一排有 $$$n$$$ 椅子,最初都没有标记。

给你一个长度为 $$$n$$$ 的排列 $$$p$$$$$$^{\text{∗}}$$$。

现在,你玩一个游戏。您从 $$$1$$$-st 椅子开始按顺序访问每把椅子。在第 $$$i$$$ 位椅子上,您可以执行以下操作:

  • 如果第$$$i$$$张椅子已经被标记,那么你无需坐在上面就立即结束游戏。
  • 否则,您可以选择坐在椅子上或跳过它并移到下一张椅子上。
  • 如果您选择坐在椅子上,那么站起来后,您将标记第$$$p_i$$$张椅子并移至下一张椅子。
如果所有 $$$n$$$ 椅子都被访问过,则游戏结束。

你的任务是确定你可以坐的椅子的最大数量。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — 椅子的数量。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2,\ldots,p_{n}$$$ — 排列 $$$p$$$。

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

输出

输出一个整数——你可以坐的椅子的最大数量。

示例

输入
复制

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

输出
复制

2
2
3
1

注意

在第一个测试用例中,您可以按如下方式进行:

  1. 你访问第 $$$1$$$-rd 椅子,坐在上面,并标记第 $$$3$$$-rd 椅子。
  2. 您访问第 $$$2$$$-nd 椅子,坐在上面,并标记第 $$$2$$$-nd 椅子。
  3. 您访问了$$$3$$$-rd 椅子。既然被标记了,你就结束了游戏。
因此,使用此序列,您总共可以坐在 $$$2$$$ 椅子上。可以证明,使用任何移动序列的椅子的最大数量是$$$2$$$。

在第二个测试用例中,您可以按如下方式进行:

  1. 你访问第 $$$1$$$-st 椅子,坐在上面,并标记第 $$$4$$$-th 椅子。
  2. 你访问了第 $$$2$$$-nd 椅子并跳过它。
  3. 您访问第 $$$3$$$-rd 椅子,坐在上面,并标记第 $$$2$$$-nd 椅子。
  4. 您访问了第 $$$4$$$ 位椅子。既然被标记了,你就结束了游戏。
因此,使用此序列,您总共可以坐在 $$$2$$$ 椅子上。可以证明,使用任何移动序列的椅子的最大数量是$$$2$$$。