题目描述

若干名学生参加体育训练。训练开始时，场馆中有 $n$ 名学生，之后训练过程中还会有 $q$ 名学生依次加入。所有 $n+q$ 名学生的身高互不相同，按照身高从低到高将他们编号为 $1$ 到 $n+q$。

训练时，学生们从左到右排成一行。根据他们的排列顺序，某些学生对会成为允许配对。

设两个学生分别站在位置 $i$ 和 $j$，其中 $i<j$。如果满足下列条件之一，则这对学生是允许配对：

• 位于第 $i$ 个位置的学生，是所有站在第 $j$ 个位置左侧且比第 $j$ 个位置学生矮的学生中，最靠左的一个；
• 位于第 $j$ 个位置的学生，是所有站在第 $i$ 个位置右侧且比第 $i$ 个位置学生矮的学生中，最靠右的一个。

例如，如果队列中学生编号从左到右为

[6, 7, 3, 5, 1, 2]

那么允许配对为 $(6,2),(6,7),(7,2),(3,2),(3,5),(5,2),(1,2)$。

训练有两个难度等级，每个等级有自己的允许传球规则。无论在哪个难度等级，同一次训练过程中都禁止把球传给已经持有过球的学生。

• 难度等级 $1$：学生可以把球传给与自己形成允许配对且比自己矮的学生。
• 难度等级 $2$：学生可以把球传给与自己形成允许配对的任意学生。

例如，队列为 [6, 7, 3, 5, 1, 2] 时：

• 在难度等级 $1$ 下，编号为 $3$ 的学生只能把球传给编号为 $2$ 的学生；编号为 $5$ 的学生可以把球传给编号为 $3$ 和 $2$ 的学生；编号为 $1$ 的学生不能传给任何人。
• 在难度等级 $2$ 下，编号为 $3$ 的学生可以把球传给编号为 $2$ 和 $5$ 的学生；编号为 $5$ 的学生可以把球传给编号为 $3$ 和 $2$ 的学生；编号为 $1$ 的学生可以把球传给编号为 $2$ 的学生。

一次训练过程如下：教练选择难度等级 $t$。某个学生拿到球并进行一次允许传球；收到球的学生继续进行允许传球，如此进行，直到无法继续。若有多个允许传球对象，可以任选其一，但不能传给本次训练中已经持有过球的学生。当前在场的学生会选择传球方式，使传球次数最大。

之后，$q$ 次有新学生加入。每次新学生会站到当前队列的最左端或最右端。加入后，训练在相同难度等级下重新进行。

你需要求出初始队列以及每次加入新学生之后，学生们最多能够完成多少次传球。

输入格式

第一行包含一个整数 $t$，表示训练难度等级。

第二行包含两个整数 $n,q$，分别表示初始参加训练的学生数量和之后加入的学生数量。

第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始队列从左到右的学生编号。保证这些编号互不相同。

接下来 $q$ 行，每行包含一个字符和一个整数，格式为 L x 或 R x：

• L x 表示编号为 $x$ 的学生加入并站到队列最左端；
• R x 表示编号为 $x$ 的学生加入并站到队列最右端。

保证每次加入后，所有在队列中的学生编号互不相同。

输出格式

第一行输出一个整数，表示初始 $n$ 名学生在难度等级 $t$ 下能够完成的最大传球次数。

接下来 $q$ 行，每行输出一个整数，表示每次加入一名学生后，在相同难度等级下能够完成的最大传球次数。

数据范围

• $1\le t\le 2$；
• $1\le n\le 10^5$；
• $0\le q\le 2\cdot 10^5$；
• $1\le a_i\le n+q$；
• 每次加入的 $x$ 满足 $1\le x\le n+q$。

样例 1

输入

1
6 2
6 7 3 5 1 2
L 8
R 4

输出

3
3
5

样例 2

输入

2
6 2
6 7 3 5 1 2
L 8
R 4

输出

4
4
6

样例 3

输入

1
5 4
4 3 1 6 2
R 7
L 8
R 9
L 5

输出

3
3
4
5
4

样例 4

输入

2
5 4
9 4 6 8 2
R 1
L 7
R 5
R 3

输出

4
4
5
7
6

样例说明

样例 1 中，一种最优方式是从编号为 $5$ 的学生开始。第一次传给编号为 $3$ 的学生，第二次传给编号为 $2$ 的学生，第三次传给编号为 $1$ 的学生。将编号为 $8$ 的学生加入左侧后，最大传球次数不变。将编号为 $4$ 的学生加入右侧后，可以从编号为 $7$ 的学生开始，依次传给编号为 $6,4,3,2,1$ 的学生。

样例 2 中，也可以从编号为 $5$ 的学生开始，传球给编号为 $3,2,7,6$ 的学生。将编号为 $8$ 的学生加入左侧后，最大传球次数不变；将编号为 $4$ 的学生加入右侧后，可以从编号为 $7$ 的学生开始，依次传球给编号为 $6,4,5,3,2,1$ 的学生。

子任务

子任务	分值	$t$	附加限制	依赖子任务
1	6	1	$n+q\le 16$	无
2	4		$n,q\le 100$	1
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 50000$	1-4
9	8		无	1-8
10	4	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			初始集合、初始顺序、剩余学生的加入顺序与加入方向均随机
17	7		$n,q\le 50000$	10-13
18	4		无	10-17