Problem J
ジャンプの振り付け

ご存知のとおり、カエルは動物の国で最も目立ちたがり屋だ。以前、カエルは組体操で塔を作って他の動物に見せつけた。しかし、カエルの王は次のBenelux Amphibian Pillaring Ceremony(BAPC)でそれ以上のパフォーマンスを行おうとしている。

彼はカエルたちに異なるダンスをさせ、そのクライマックスにすべてのカエルが塔を作るようにした。あなたは振付師として、カエルに振り付けをトレーニングしている。 カエルのダンスは一列にならんで行う。カエルは順番にジャンプを行い、各ジャンプでは左右いずれかの方向に行う。カエルの王はこのダンスをもっと興味深いものにしようとした。

まず、彼はカエルにジャンプの距離を順々に伸ばすように指示した。すなわち、最初のジャンプは距離1、2番目のジャンプは距離2、3番目のジャンプは距離3、ということだ。 次に、ダンスはすべてのカエルが一つの大きな塔になった時点で終了する。 次に、ダンスを派手で印象的にするため、合計のジャンプの回数は最も少なくする。

王は完璧主義者であるため、ダンスも完璧にしたい。 彼はあなたに優秀なダンサーのチームを与え、各カエルの開始位置および塔を作る位置を指示した。しかし、王はダンスに満足していないようで、毎日リハーサルを見ては変更を行っている。ダンスが上手なカエルを加えたり、パフォーマンスが出ていないカエルを外したり、時には塔の位置を気に入った場所に変えたりしている。

毎日の終わりに、王はダンスを最も効率的な方法、すなわちジャンプの回数を最小にする方法を知りたがっている。

入力

• 先頭行は $0 \leq n \leq 5000$ と $0\leq t\leq 10^6$の$2$つの整数で、初期のカエルの数と初期の塔の位置を表す。

• $2$ 行目は $0\leq p_ i\leq 10^6$ の $n$ 個の整数で、各カエルの初期の位置を表す。

• $3$ 行目は $0\leq C\leq 10^6$ の整数で、王が行う変更の回数を表す。

• その後 $C$ 行は以下の$3$種類のいずれかの形式となる。

  • $+$ $a$ という形式の場合、王は位置 $a$にカエルを追加する。

  • $-$ $a$ という形式の場合、王は位置 $a$のカエルを除去する。除去する位置にはカエルが最低でも1匹いると仮定してよい。

  • $\mathrm t$ $a$ という形式の場合、王は塔を位置 $a$ に変更する。

  各ケースにおいて、$a$ は $0$ 以上 $10^6$ 以下の値をとる。 王がカエルの追加もしくは削除を行う回数は $5000$ 回以下であることは保証される。

出力

$C$ 回のそれぞれの変更について、ジャンプの最小回数を出力する。

1 1
0
7
t 0
t 1
t 2
t 3
t 4
t 5
t 6

0
1
3
2
3
5
3

3 0
2 6 6
10
t 1
t 2
t 3
t 4
t 5
t 6
t 7
t 8
t 9
t 10

11
6
5
9
4
3
7
9
9
10

0 0

7
t 3
+ 4
t 5
+ 6
t 2
- 4
t 1

0
1
1
2
6
3
5