動物園管理員矮人最近被拔擢為弗羅茨瓦夫動物園狐狸館的館長。他對狐狸（波蘭語稱為 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$。