#P17919. Foxes

Foxes

Foxes

有 NN 只狐狸从左到右排成一行,第 ii 只狐狸的魅力值为 mim_i。

饲养员初始站在最左边、即第 11 个位置。他依次执行 QQ 个操作,每次操作是以下三种之一:

  • <:向左移动一个位置。
  • >:向右移动一个位置。
  • ! v:将当前位置狐狸的魅力值改为 vv。

每次执行 ! 操作后,求当前整行魅力值序列的最长严格递增子序列长度。

子序列可以不连续,但所选位置的下标必须递增,并且所选魅力值也必须严格递增。

输入格式

第一行两个整数 N,QN,Q。

第二行 NN 个整数 m1,m2,…,mNm_1,m_2,\ldots,m_N,表示初始魅力值。

接下来 QQ 行,每行一个操作,格式如题面所述。移动操作均合法,不会使饲养员离开这 NN 个位置。

输出格式

对每个 ! 操作,输出一行一个整数,表示修改后整行序列的最长严格递增子序列长度。

初始状态及移动操作不需要输出。若没有 ! 操作,则不输出任何内容。

数据范围

  • 2≤N≤2000002\le N\le200000。
  • 1≤Q≤5000001\le Q\le500000。
  • 1≤mi≤1061\le m_i\le10^6,1≤v≤1061\le v\le10^6。
  • 每个输入文件只有一组数据。

样例

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

三次修改分别发生在第 22、55、44 个位置。