動物園管理員矮人最近升職做咗弗羅茨瓦夫動物園狐狸館嘅館長。佢對狐狸（波蘭文叫做 lis）嘅熱愛簡直係無止境嘅。

呢位矮人負責照顧沿住主通道排列嘅一長排狐狸圍欄入面嘅狐狸。每隻狐狸都有一個華麗值，而矮人最自豪嘅就係喺佢嘅狐狸入面搵出華麗值嘅最長遞增子序列（LIS）。

今日，矮人要將一啲狐狸轉移去其他動物園，並用其他動物園送返嚟嘅狐狸替換佢哋。喺一日開始嗰陣，動物園管理員矮人推住一車新狐狸企喺第一個（最左邊）圍欄隔離。矮人會沿住通道行，由一個圍欄移動去另一個圍欄。有時，佢會喺某個圍欄前面停低，並將嗰度嘅狐狸換成另一隻可能具有唔同華麗值嘅狐狸。每次發生呢種情況嗰陣，佢都必須立即計算出最長遞增華麗值子序列嘅長度。你能唔能夠幫佢記錄住呢個數字？

輸入格式

輸入嘅第一行包含兩個整數 $N$ 同 $Q$，分別代表沿住通道嘅圍欄數量同埋矮人採取嘅行動次數。

輸入嘅第二行包含 $N$ 個整數 $m_1, m_2, \dots, m_N$，描述每隻狐狸嘅初始華麗值。

接落嚟嘅 $Q$ 行描述各個行動。單一行動係以下其中一種：

1. < — 矮人向左移動一個圍欄，
2. > — 矮人向右移動一個圍欄，
3. ! v — 矮人將目前圍欄入面嘅狐狸換成一隻華麗值為 $v$ 嘅狐狸。

輸出格式

對於每個 ! 行動，輸出一行，包含狐狸華麗值嘅最長遞增子序列嘅長度。

數據範圍

$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$。跟住佢移動到第五個圍欄，並將狐狸換成一隻華麗值為 $10$ 嘅狐狸，LIS 嘅長度變成 $3$。最後，管理員移動到第四個圍欄並將華麗值改為 $11$，令 LIS 嘅長度再次變成 $2$。