003 - AC MONKEY BABYS

問題文

左から右に向かって$1$から$N$の番号が付いたマスがあります。
マス$i$にはサル$i$がいます。また、サル$i$は自分の群れを表す数字$A_i$を持っています。

高橋君はこのサルの生態を調査し、以下の点に気付きました。

• 左右のマスにしか移動しない
• 同じ群れのサルはみな同じように行動する。即ち、$A_i = A_j$であるようなサル$i$とサル$j$は同じ行動を取る
• マス$1$から左に移動したり、マス$N$から右に移動しようとしたサルははみ出し者とみなされ、二度とマスの中には戻れない

サルの行動ログが$Q$個与えられます。

$i$個めの行動ログは移動した群れの番号$t_i$, 移動した方向$d_i$からなります。

$d_i$が'L'のときに左に、$d_i$が'R'のとき右に移動します。

$Q$回の行動が終わった後、マスの外に出たサルの総数を求めてください。

制約

• $1 ≦ N ≦ 2 * 10^5$
• $1 ≦ Q ≦ 2 * 10^5$
• $1 ≦ A_i ≦ N$
• $t_i∈A$
• $d_i$は'L'または'R'

入力

入力は以下の形式で、標準入力より与えられる。

N Q
A1 A2 ... AN
t1 d2
t2 d2
:
tQ dQ

出力

$Q$回の行動が終わった後、マスの外に出たサルの総数を1行に出力せよ

改行を忘れないよう気を付けること

入出力例

入力1

5 3
5 3 1 5 1
1 R
5 L
5 L

出力1

2

入力2

10 5
1 6 2 9 1 7 5 9 4 2
6 L
6 L
9 R
9 R
9 R

出力2

2