一排有 $$$n$$$ 椅子,最初都没有标记。
给你一个长度为 $$$n$$$ 的排列 $$$p$$$$$$^{\text{∗}}$$$。
现在,你玩一个游戏。您从 $$$1$$$-st 椅子开始按顺序访问每把椅子。在第 $$$i$$$ 位椅子上,您可以执行以下操作:
- 如果第$$$i$$$张椅子已经被标记,那么你无需坐在上面就立即结束游戏。
- 否则,您可以选择坐在椅子上或跳过它并移到下一张椅子上。
- 如果您选择坐在椅子上,那么站起来后,您将标记第$$$p_i$$$张椅子并移至下一张椅子。
你的任务是确定你可以坐的椅子的最大数量。
$$$^{\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$$$。
输出
输出一个整数——你可以坐的椅子的最大数量。
示例
输入复制
433 2 154 3 2 5 144 2 1 342 3 4 1
输出复制
2231
注意
在第一个测试用例中,您可以按如下方式进行:
- 你访问第 $$$1$$$-rd 椅子,坐在上面,并标记第 $$$3$$$-rd 椅子。
- 您访问第 $$$2$$$-nd 椅子,坐在上面,并标记第 $$$2$$$-nd 椅子。
- 您访问了$$$3$$$-rd 椅子。既然被标记了,你就结束了游戏。
在第二个测试用例中,您可以按如下方式进行:
- 你访问第 $$$1$$$-st 椅子,坐在上面,并标记第 $$$4$$$-th 椅子。
- 你访问了第 $$$2$$$-nd 椅子并跳过它。
- 您访问第 $$$3$$$-rd 椅子,坐在上面,并标记第 $$$2$$$-nd 椅子。
- 您访问了第 $$$4$$$ 位椅子。既然被标记了,你就结束了游戏。