いくつかの生徒がスポーツクラブに参加している。トレーニング開始時には体育館に $n$ 人の生徒がおり、その後セッション中に $q$ 人の生徒が一人ずつ加わる。$n+q$ 人の生徒の身長はすべて異なっており、背の順に生徒に $1$ から $n+q$ までの番号を付ける。
トレーニング中、生徒たちはボールを使った運動を行う。生徒はある順序で左から右へ一列に並ぶ。並ぶ順序に応じて、いくつかの生徒のペアが 有効なペア を形成する。
位置 $i$ と $j$ ($i < j$) に立っている生徒のペアは、次の2つの条件のいずれかを満たす場合に有効なペアとなる：
- 位置 $i$ の生徒が、位置 $j$ の生徒よりも背が低く、かつその左側にいる生徒の中で最も左にいる場合；
- 位置 $j$ の生徒が、位置 $i$ の生徒よりも背が低く、かつその右側にいる生徒の中で最も右にいる場合。
例えば、番号 $[6, 7, 3, 5, 1, 2]$ の生徒が一列に並んでいる場合、有効なペアは $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$, $(1, 2)$ である。
この運動には2つの難易度レベルがあり、それぞれに独自の 有効なスロー がある。どちらの難易度レベルで運動を行う場合でも、現在の運動中にすでにボールを保持したことがある生徒にボールを投げることは禁止されている。
第1の難易度レベルでは、生徒は自分と有効なペアを形成し、かつ自分よりも背が低い生徒にのみボールを投げることができる。例えば、番号 $[6, 7, 3, 5, 1, 2]$ の生徒が一列に並んでいる場合、番号 $3$ の生徒は番号 $2$ の生徒にのみボールを投げることができ、番号 $5$ の生徒は番号 $3$ と $2$ の生徒に投げることができ、番号 $1$ の生徒は誰にも投げることができない。
第2の難易度レベルでは、生徒は自分と有効なペアを形成する任意の生徒にボールを投げることができる。例えば、番号 $[6, 7, 3, 5, 1, 2]$ の生徒が一列に並んでいる場合、番号 $3$ の生徒は番号 $2$ と $5$ の生徒に投げることができ、番号 $5$ の生徒は番号 $3$ と $2$ の生徒に投げることができ、番号 $1$ の生徒は番号 $2$ の生徒に投げることができる。
運動は次のように行われる。コーチが難易度レベル $t$ を選ぶ。ある生徒がボールを持ち、有効なスローを行う。ボールを受け取った生徒がさらに有効なスローを行い、以下同様に続ける。スローは可能な限り続けられる。複数の有効なスローがある場合はいずれも選択できるが、現在の運動中にすでにボールを保持したことのある生徒にボールを投げることは禁止されている。トレーニング参加者は、選ばれた難易度レベルにおいて、最大のスロー回数が達成されるように有効なスローを行う。
その後、$q$ 回にわたって、さらに一人の生徒がトレーニングに加わる。その生徒は、すでに運動を行っている生徒たちの左側または右側に立つ。その後、同じ難易度レベルで再び運動が行われる。
初期の参加者の集合について、および新しい生徒が加わるたびに、トレーニング参加者が行うことのできるスローの最大回数を求める必要がある。
入力
最初の行には単一の整数 $t$ ($1 \le t \le 2$) が含まれる — 運動の難易度レベルである。
2行目には2つの整数 $n$ と $q$ ($1 \leq n \leq 10^{5}$, $0 \leq q \leq 2 \cdot 10^{5}$) が含まれる — 初期の参加者数と加わる参加者の数である。
3行目には $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$ 行には、$q$ 人の参加者がそれぞれ追加された後、同じ難易度レベルで運動を行った場合の問題の答えである整数をそれぞれ1行ずつ出力せよ。
入出力例
入力例 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番目は番号2の参加者へ、3番目は番号1の参加者へ行うことができる。左側に参加者8を追加しても最大スロー回数は増加しない。右側に参加者4を追加すると、番号7の参加者から始めて、番号6, 4, 3, 2, 1の参加者へ順にボールを投げることができる。
2番目の例では、やはり番号5の参加者から始めて、番号3, 2, 7, 6の参加者への4回の有効なスローを得ることができる。左側に参加者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 |