几个学生参加一个体育俱乐部。训练开始时，体育馆里有 $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 \leq n \leq 10^{5}$，$0 \leq q \leq 2 \cdot 10^{5}$）—— 初始参与人数以及将要加入的参与人数。

第三行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$1 \leq a_{i} \leq n + q$）—— 初始站成一排的参与者的编号，从左到右。保证所有编号互不相同。

接下来的 $q$ 行每行包含加入练习的参与者的信息。每行由一个字符 'L' 或 'R' 和一个整数 $x$ 组成，中间用空格分隔（$1\le x\le n + q$）。字母 'L' 表示编号为 $x$ 的学生站在队伍的最左边，'R' 表示站在最右边。

保证每次加入后，所有参与者的编号互不相同。

输出格式

第一行输出一个数 —— 对于初始 $n$ 名参与者和练习难度 $t$ 的问题答案。

接下来 $q$ 行，每行输出一个整数 —— 在加入每名新参与者后，以相同难度级别进行练习的问题答案。

样例

输入 1

1
3 2
6 3 2
L 8
R 4

输出 1

2
2
3

输入 2

2
3 2
6 3 2
L 8
R 4

输出 2

2
2
4

说明

在第一个样例中，最优策略是从例如编号为 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 的参与者。

子任务