Dwarf the Zookeeper 最近被提升为弗罗茨瓦夫动物园狐狸馆的馆长。他对狐狸（波兰语称为 lis）的热爱无以复加。

这位矮人负责照看沿主路排列的一长排狐狸围栏。每只狐狸都有一个“华丽值”，矮人以能找出他所养狐狸中华丽值的最长上升子序列（LIS）为荣。

今天，矮人正在将一些狐狸转移到其他动物园，并用其他动物园送来的狐狸替换它们。一天开始时，Dwarf the Zookeeper 推着一车新狐狸站在第一个（最左侧）围栏旁。矮人将沿着小路行走，从一个围栏移动到另一个围栏。有时，他会停在某个围栏前，用另一只狐狸替换那里的狐狸，新狐狸的华丽值可能不同。每次发生这种情况时，他都必须立即计算出华丽值的最长上升子序列的长度。你能帮他记录这个数字吗？

输入格式

第一行包含两个整数 $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

说明

首先，Dwarf the Zookeeper 移动到第二个围栏，并将狐狸换成华丽值为 2 的狐狸。此时最长上升子序列的长度为 2。然后他移动到第五个围栏，并将狐狸换成华丽值为 10 的狐狸，LIS 的长度变为 3。最后，Zookeeper 移动到第四个围栏，将华丽值改为 11，使得 LIS 的长度再次变为 2。