题目描述

Not every student wants to be just another brick.
—— Pink Floyd

在这所热爱秩序的学校里，学生最理想的状态，是像砖一样整齐地嵌进队伍里：间距一致、前后紧密、没有空缺，最好连表情都不要太丰富。

某天课间，班长云小斗奉命在操场上组织班里 $n$ 名同学站队。

最初，所有同学按既定顺序排成一列。每位同学都有一个互不相同的年级成绩排名，排名越小，说明成绩越好。

然而，老师迟迟没有出现。失去了外部约束后，队伍开始缓慢而无声地崩坏。

有人为了躲开前排的“重点关注区”，悄悄从原位置离开，并绕到当前队伍的最末尾；于是原先的位置留下了空缺。更糟糕的是，剩下的人沉浸在自己的世界里，并不会主动向前填补这些空位。于是，这支队伍逐渐变得像一条断裂的流水线：顺序尚存，缝隙却越来越多。

在这个过程中，一些同学偶尔会向班长云小斗提出一个问题：在自己当前所处位置之前，成绩最好的同学是谁。形式化地说，就是询问自己前方所有仍在队伍中的同学里，年级成绩排名最小的是哪一位。

终于，老师来了。所有人以可以忽略不计的时间收起了手机，假装一切秩序如常。老师并不关心整支队伍整体向后偏移了多少，只关心从队首到队尾看上去是否是一段连续、没有空缺的队列。

为了尽快平息事态，老师要求云小斗重新整顿队伍。一次移动可以选择任意一名同学，将其移动到任意一个空缺位置上。你需要帮助云小斗：

1. 回答所有同学提出的询问；
2. 在所有操作结束后，计算至少需要移动多少名同学，才能使队伍重新变得整齐。

输入格式

从文件 queue.in 中读入。

第一行两个整数 $n,m$，表示共有 $n$ 名同学，且在老师到来之前一共发生了 $m$ 次事件。

第二行包含 $n$ 个以空格分隔的整数 $a_i$，表示初始时从前到后第 $i$ 名同学的年级成绩排名。数据保证这些排名两两不同。

接下来 $m$ 行，每行描述一个事件。每个事件由一个字符 $op$ 和一个整数 $x$ 构成，其含义如下：

• 若 $op=\textit{A}$，年级成绩排名为 $x$ 的同学发出询问：自己前方成绩最好的同学是谁？
• 若 $op=\textit{M}$，年级成绩排名为 $x$ 的同学离开当前位置，移动到当前队伍的最末尾。

保证每次 $\textit{M}$ 操作发生时，排名为 $x$ 的同学当前不在队尾。

输出格式

输出到文件 queue.out 中。

对于输入中的每个询问操作，按出现顺序输出一行一个整数，表示所询问同学前方成绩最好的同学的年级成绩排名。若其前方不存在任何同学，则输出 -1。

最后输出一行一个整数，表示在全部事件结束后，至少需要移动多少名同学，才能使队伍重新变为连续、没有空缺的一列。

输入输出样例

输入样例 1

4 5
23 150 37 301
A 37
M 23
M 37
A 301
A 37

输出样例 1

23
150
23
1

样例 1 说明

初始队伍为：

$[23,150,37,301]$

• 操作 A 37：在 $37$ 前方的同学为 $23,150$，其中成绩最好的同学对应最小的年级成绩排名，因此答案为 $23$；
• 操作 M 23：$23$ 离开原位置并移动到队尾，队伍变为 $[150,37,301,23]$，原位置留下空缺；
• 操作 M 37：$37$ 离开原位置并移动到队尾，队伍变为 $[150,301,23,37]$，其原位置同样留下空缺；
• 操作 A 301：在 $301$ 前方的同学只有 $150$，故答案为 $150$；
• 操作 A 37：在 $37$ 前方的同学为 $150,301,23$，其中成绩最好的同学为 $23$。

所有操作结束后，当前队伍对应的位置上已经出现空缺。至少移动 $1$ 名同学填补空缺，才能使队伍重新整齐。

数据范围和约定

• 对于 $20\%$ 的数据，满足 $1 \le n,m \le 1000$；
• 对于另外 $30\%$ 的数据，满足所有事件均为询问操作；
• 对于 $100\%$ 的数据，满足 $1 \le n,m \le 10^5$，且初始成绩排名互不相同。