CF1824A LuoTianyi and the Show
题目描述
有 $n$ 个人观看一场与 VOCALOID 有关的演出，场地里有一行座位，从左到右标号 $1$ 到 $m$，接下来观众将按顺序以如下三种方式中的一种选择座位：
1. 如果没人坐在座位上，就坐在座位 $m$ 上，否则坐在目前最靠左的人的左边。若座位 $1$ 有人，则离开。
2. 如果没人坐在座位上，就坐在座位 $1$ 上，否则坐在目前最靠右的人的右边。若座位 $m$ 有人，则离开。
3. 如果 $x_i$ 没人则坐在 $x_i$，否则离开。
现在知道每个人选择座位的方式，你可以让人们按照任意顺序入场，求最多找到座位的人数。
输入格式
每一个测试点有多组测试数据，第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) 为测试数据的组数。
每组数据格式如下：
第一行包含两个整数 $n$ 和 $m$ ( $1 \le n, m \le 10^5$ )，分别为人数和座位数。
第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$ ( $-2 \le x_i \le m$ , $x_i \ne 0$ ) 表示观众入座方式，第 $i$ 个人入座的方式如下：
1. 如果 $x_i=-1$，那么第 $i$ 个人以第一种方式选择座位。
2. 如果 $x_i=-2$，那么第 $i$ 个人以第二种方式选择座位。
3. 如果 $x_i > 0$，那么第 $i$ 个人选择第 $x_i$ 个座位并以第三种方式选择座位。
保证每组数据中 $n$ 和 $m$ 的总和不超过 $10^5$。
输出格式
每一组测试数据输出一个整数，表示这组数据中找到座位的最多人数。
说明/提示
第一组测试样例中，所有人都想占用座位 $5$，因此只有 $1$ 个人能找到座位。
第二组测试样例中，我们可以让人们按照 $1,2,3,4$ 的顺序入场，那么除了最后一个人以外的人都能找到座位。
在第三组测试样例中，我们可以让人们按照这样的顺序入场：
让第三个人入场：
| – | – | – | 3 | – | – | – |
| --- | --- | --- | --- | --- | --- | --- |
让第四个人入场：
| – | – | – | 3 | 4 | – | – |
| --- | --- | --- | --- | --- | --- | --- |
让第五个人入场：
| – | – | – | 3 | 4 | 5 | – |
| --- | --- | --- | --- | --- | --- | --- |
让第一个人入场：
| – | – | 1 | 3 | 4 | 5 | – |
| --- | --- | --- | --- | --- | --- | --- |
让第二个人入场：
| – | 2 | 1 | 3 | 4 | 5 | – |
| --- | --- | --- | --- | --- | --- | --- |
于是 $5$ 个人都找到了座位。
在第五组测试样例中，我们可以让人们按照这样的顺序入场：
让第四个人入场：
| – | – | – | – | 4 | – |
| --- | --- | --- | --- | --- | --- |
让第三个人入场：
| – | – | – | 3 | 4 | – |
| --- | --- | --- | --- | --- | --- |
让第六个人入场，由于他选择了第四个座位按照第三种方式入场，但第四个座位已经被占，所以离开：
| – | – | – | 3 | 4 | – |
| --- | --- | --- | --- | --- | --- |
让第五个人入场：
| – | – | 5 | 3 | 4 | – |
| --- | --- | --- | --- | --- | --- |
让第一个人入场：
| – | 1 | 5 | 3 | 4 | – |
| --- | --- | --- | --- | --- | --- |
让第二个人入场：
| 2 | 1 | 5 | 3 | 4 | – |
| --- | --- | --- | --- | --- | --- |
于是 $5$ 个人找到了座位。
在第七组测试样例中，我们可以让人们按照这样的顺序入场：
让第三个人入场：
| 3 | – | – | – | – | – | – |
| --- | --- | --- | --- | --- | --- | --- |
让第四个人入场：
| 3 | 4 | – | – | – | – | – |
| --- | --- | --- | --- | --- | --- | --- |
让第五个人入场：
| 3 | 4 | 5 | – | – | – | – |
| --- | --- | --- | --- | --- | --- | --- |
让第六个人入场：
| 3 | 4 | 5 | 6 | – | – | – |
| --- | --- | --- | --- | --- | --- | --- |
让第一个人入场：
| 3 | 4 | 5 | 6 | 1 | – | – |
| --- | --- | --- | --- | --- | --- | --- |
让第二个人入场，他以第一种方式选择座位，而座位 $1$ 被占用，所以离开：
| 3 | 4 | 5 | 6 | 1 | – | – |
| --- | --- | --- | --- | --- | --- | --- |
于是 $5$ 个人找到了座位。