飼育員ドワーフは最近、ヴロツワフ動物園のキツネ館の館長に昇進しました。彼のキツネ（ポーランド語では lis と呼ばれます）に対する愛は留まるところを知りません。

ドワーフはメイン通路に沿って並んだ囲いの中にいる長い列のキツネたちを世話しています。各キツネには素晴らしさ（magnificence）の値があり、ドワーフはキツネたちの素晴らしさの最長増加部分列（LIS）を見つけることに誇りを持っています。

今日、ドワーフは何匹かのキツネを他の動物園へ移送し、代わりに他の動物園から送られてきたキツネと入れ替えています。一日の終業開始時、飼育員ドワーフは新しいキツネを乗せたカートを持って最初（一番左）の囲いの隣に立っています。ドワーフは通路に沿って歩き、囲いから囲いへと移動します。時々、彼はいずれかの囲いの前で立ち止まり、そこにいるキツネを（おそらく異なる素晴らしさを持つ）別のキツネと入れ替えます。これが行われるたびに、彼は直ちに素晴らしさの最長増加部分列の長さを計算しなければなりません。彼がこの数値を記録し続けるのを手伝ってくれますか？

入力

入力の $1$ 行目には、通路に沿った囲いの数とドワーフが行う行動の数を表す $2$ つの整数 $N$ と $Q$ が含まれます。

入力の $2$ 行目には、各キツネの初期の素晴らしさを表す $N$ 個の整数 $m_1, m_2, \dots, m_N$ が含まれます。

続く $Q$ 行は行動を表します。$1$ 回の行動は次のいずれかです：

1. < — ドワーフは左へ $1$ つ囲いを移動する。
2. > — ドワーフは右へ $1$ つ囲いを移動する。
3. ! v — ドワーフは現在の囲いにいるキツネを、素晴らしさ $v$ のキツネと交換する。

出力

各 ! の行動について、キツネたちの素晴らしさの最長増加部分列の長さを $1$ 行に出力してください。

制約

$2 \le N \le 200\,000$、$1 \le Q \le 500\,000$、$1 \le m_i \le 10^6$、$1 \le v \le 10^6$。

入出力例

入力例 1

5 8
3 4 1 7 2
>
! 2
>
>
>
! 10
<
! 11

出力例 1

2
3
2

注記

最初に、飼育員ドワーフは $2$ 番目の囲いに移動し、キツネを素晴らしさ $2$ のキツネと交換します。最長増加部分列の長さは $2$ です。次に彼は $5$ 番目の囲いに移動してキツネを素晴らしさ $10$ のキツネと交換し、LIS の長さは $3$ になります。最後に、飼育員は $4$ 番目の囲いに移動して素晴らしさを $11$ に変更し、LIS の長さは再び $2$ になります。