CF2210B Simply Sitting on Chairs
题目描述
这里有一行 $n$ 把椅子。初始时全部没有被标记。
有一个长度为 $n$ 的排列 $p$。
现在，你在玩一个游戏。从第一把椅子开始顺序考虑，在第 $i$ 把椅子处，你可以：
- 如果第 $i$ 把椅子已经被标记，立即结束游戏。
- 否则，你可以继续或坐在第 $i$ 把椅子上。
- 如果你选择坐下，标记第 $p_i$ 把椅子并走到下一把椅子。
如果所有椅子都已经考虑过，结束游戏。给出你可以坐下的最大椅子数量。
输入格式
第一行一个正整数 $T$（$1\le T\le10^4），表示数据组数。
对于每组数据：
第一行一个正整数 $n$（$1\le n\le2\times10^5$）。
接下来一行 $n$ 个正整数表示排列 $p$。
保证 $n$ 的总和不超过 $2\times10^5$。
输出格式
对于每组数据，一行一个整数表示答案。
说明/提示
在第一组数据中，你可以：
1. 坐在第 $1$ 把椅子上，标记第 $3$ 把椅子。
2. 坐在第 $2$ 把椅子上，标记第 $2$ 把椅子。
3. 考虑第 $3$ 把椅子，由于其已经被标记，结束游戏。
这样，你可以坐在 $2$ 把椅子上，可以证明这是最大的。
在第二组数据中，你可以：
1. 坐在第 $1$ 把椅子上，标记第 $4$ 把椅子。
2. 跳过第 $2$ 把椅子。
3. 坐在第 $3$ 把椅子上，标记第 $2$ 把椅子。
4. 考虑第 $4$ 把椅子，由于其已经被标记，结束游戏。
这样，你可以坐在 $2$ 把椅子上，可以证明这是最大的。