P17021 [ROI 2026 Day1] 体育训练

有若干名学生在体育兴趣小组中进行训练。训练开始时，体育馆内有 $n$ 个人，随后在课程中陆续加入了 $q$ 个人。所有 $n + q$ 名学生的身高互不相同，我们将他们按身高递增顺序编号为 $1$ 到 $n + q$。 训练中，学生们进行一项传球练习。他们按某种顺序从左到右排成一行。根据他们排列的顺序，某些学生对会构成**合法对**。 若 $i < j$，位于位置 $i$ 和 $j$ 的两名学生构成合法对，当且仅当满足以下两个条件之一： - 位置 $i$ 的学生，是位于位置 $j$ 的学生左侧且比他矮的学生中，最靠左的那一个； - 位置 $j$ 的学生，是位于位置 $i$ 的学生右侧且比他矮的学生中，最靠右的那一个。 例如，若排成一行的学生编号依次为 $[6, 7, 3, 5, 1, 2]$，则合法对包括 $(6, 2)$、$(6, 7)$、$(7, 2)$、$(3, 2)$、$(3, 5)$、$(5, 2)$ 和 $(1, 2)$。 该练习有两个难度等级，每个等级有各自允许的**合法传球**。在任意难度等级的练习过程中，禁止将球传给已经接过球的学生。 在第一个难度等级下，学生只能将球传给他所构成合法对中比他矮的人。例如，若排成一行的学生编号为 $[6, 7, 3, 5, 1, 2]$，则编号 $3$ 的学生只能传给编号 $2$；编号 $5$ 的学生可以传给 $3$ 和 $2$；编号 $1$ 的学生不能传给任何人。 在第二个难度等级下，学生可以将球传给与他构成合法对的任何人。例如，在上述排列 $[6, 7, 3, 5, 1, 2]$ 中，编号 $3$ 的学生可以传给 $2$ 和 $5$；编号 $5$ 的学生可以传给 $3$ 和 $2$；编号 $1$ 的学生可以传给 $2$。 练习的过程如下：教练选定练习的难度等级 $t$。某一名学生持球，并完成一次合法传球。接到球的学生再次完成合法传球，以此类推。传球持续进行，直至无法再传为止。若有多种合法传球可选，可以任选其一，但禁止将球传给在该次练习中已经接过球的学生。参加训练的成员将以最大可能的传球次数完成该难度等级下的合法传球。 随后，有 $q$ 次新成员加入训练。每次新加入的学生站在已有队列的最左侧或最右侧。之后，练习在相同的难度等级下重新进行。 对于训练最初的人员构成，以及每次加入新学生后，都需要计算参加训练的学生最多能够完成多少次传球。

第一行包含一个整数 $t$（$1 \le t \le 2$），表示练习的难度等级。 第二行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^5$，$0 \le q \le 2 \cdot 10^5$），分别表示练习最初的参加人数和后续加入的人数。 第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n + q$），表示最初从左到右排列的学生编号。保证所有编号互不相同。 接下来的 $q$ 行描述加入的学生。每行包含一个字符 `L` 或 `R` 以及一个整数 $x$（$1 \le x \le n + q$），中间用空格隔开。`L` 表示编号为 $x$ 的学生站在队列最左侧，`R` 表示站在最右侧。 保证每次添加后，所有学生的编号依然互不相同。

第一行输出一个整数——对最初的 $n$ 名学生在难度 $t$ 下的答案。 接下来的 $q$ 行，每行输出一个整数——每次加入新学生并完成同难度练习后的答案。

### 说明 在第一个样例中，练习最优可以从编号 $5$ 的学生开始。第一次传球可以传给 $3$，第二次传给 $2$，第三次传给 $1$。在左侧加入编号 $8$ 的学生并不会增加最大传球次数。而在右侧加入编号 $4$ 的学生后，可以从编号 $7$ 开始，依次传给 $6$、$4$、$3$、$2$、$1$。 在第二个样例中，同样可以从编号 $5$ 开始，完成四次合法传球，依次传给 $3$、$2$、$7$、$6$。在左侧加入编号 $8$ 的学生不会改变最大传球次数；在右侧加入编号 $4$ 的学生后，例如从 $7$ 开始，可以依次传给 $6$、$4$、$5$、$3$、$2$、$1$。 ### 子任务 | 子任务 | 分数 | $t$ | $n$、$q$ | 额外限制 | 依赖子任务 | |:---:|:---:|:---:|:---:|:---|:---:| | 1 | 6 | $t = 1$ | $n + q \le 16$ | -- | -- | | 2 | 4 | ^ | $n, q \le 100$ | -- | 1 | | 3 | 3 | ^ | $n \le 1000$，$q = 0$ | -- | -- | | 4 | 5 | ^ | $n, q \le 1000$ | -- | 1–3 | | 5 | 3 | ^ | $q = 0$ | -- | 3 | | 6 | 10 | ^ | $n = 1$ | $a_1 = 1$；学生按编号递增顺序加入 | -- | | 7 | 6 | ^ | -- | 保证初始参加者、他们的顺序、剩余学生的加入顺序及加入方向都是随机的 | -- | | 8 | 5 | ^ | $n, q \le 50\,000$ | -- | 1–4 | | 9 | 8 | ^ | -- | -- | 1–8 | | 10 | 4 | $t = 2$ | $n + q \le 16$ | -- | -- | | 11 | 6 | ^ | $n, q \le 100$ | -- | 10 | | 12 | 5 | ^ | $n \le 1000$，$q = 0$ | -- | -- | | 13 | 9 | ^ | $n, q \le 1000$ | -- | 10–12 | | 14 | 3 | ^ | $q = 0$ | -- | 12 | | 15 | 6 | ^ | $n = 1$ | $a_1 = 1$；学生按编号递增顺序加入 | -- | | 16 | 6 | ^ | -- | 保证初始参加者、他们的顺序、剩余学生的加入顺序及加入方向都是随机的 | -- | | 17 | 7 | ^ | $n, q \le 50\,000$ | -- | 10–13 | | 18 | 4 | ^ | -- | -- | 10–17 | 翻译由 DeepSeek V4 Pro 完成