当所有燃料被填充好的时候，巨大的通用测评号恒星级宇宙飞船轰鸣了起来。你兴奋地登上飞船。章北蚤将目的地直接设为了四光年外的南门二，又名半人马座 $\alpha$。

“通用测评，前进四！”

只见通用测评号迅速驶出了港口，以 “前进四” 状态急剧加速。为了让通用测评号保持前进四状态，你需要对发动机进行一些必要的维护。

通用测评号所配备的发动机共有 $n$ 级燃烧室，编号为 $1, \dots, n$。第 $i$ 级燃烧室的下一级是第 $i-1$ 级燃烧室，第 $1$ 级燃烧室的下一级是通用测评号的喷射口，也称为 “第 $0$ 级燃烧室”。第 $i$ 级燃烧室的上一级是第 $i+1$ 级燃烧室，第 $n$ 级燃烧室没有上一级燃烧室。

每个燃烧室都会输出一部分功率给下一级的燃烧室。具体来说，设第 $i$ 级燃烧室能承受的最大功率为 $a_i$（$1 \le i \le n$），若第 $i$ 级燃烧室从上一级燃烧室获得的输入功率为 $x$，那么第 $i$ 级燃烧室对下一级燃烧室的输出功率为 $\min\{a_i, x\}$。特别地，第 $n$ 级燃烧室由燃料直接供能，输入功率非常大，可以认为是无穷大 $+\infty$。

显然，如果如果一个燃烧室的输入功率不等于输出功率，则会造成能源的浪费。所以维护发动机时统计有多少个燃烧室的输入功率不等于输出功率是非常重要的。

前进四状态下发动机状态瞬息万变，所以你需要实现一个跑得跟前进四一样快的发动机监控系统，支持下面两种操作：

• 1 x v：把第 $x$ 级燃烧室的最大功率 $a_x$ 改为 $v$；
• 2 x：询问第 $x, x+1, \dots, n$ 级燃烧室中有多少个的输入功率不等于输出功率。

人话题面： 单点修改，询问 $a_{x},\cdots,a_{n}$ 的不同的后缀最小值个数。

输入格式

第一行两个正整数 $n,Q$。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

接下来 $Q$ 行，一行若干个正整数，表示一次操作。

输出格式

对于每次操作 $2$，输出一行一个正整数表示答案。

样例一

input

3 6
1 3 3
2 1
1 2 2
2 1
1 3 1
2 1
2 2

output

2
3
1
1

explanation

第一次操作为询问操作，询问 $\{a_1,a_2,a_3\}$ 的不同后缀最小值个数。由于后缀最小值分别为 $1,3,3$，因此答案为 $2$。

第二次操作为修改操作，修改后数组 $a$ 变为 $\{1,2,3\}$。

第三次操作为询问操作，询问 $\{a_1,a_2,a_3\}$ 的不同后缀最小值个数。由于后缀最小值分别为 $1,2,3$，因此答案为 $3$。

第四次操作为修改操作，修改后数组 $a$ 变为 $\{1,2,1\}$。

第五次操作为询问操作，询问 $\{a_1,a_2,a_3\}$ 的不同后缀最小值个数。由于后缀最小值分别为 $1,1,1$，因此答案为 $1$。

第六次操作为询问操作，询问 $\{a_2,a_3\}$ 的不同后缀最小值个数。由于后缀最小值分别为 $1,1$，因此答案为 $1$。

样例二,三,四

见下发文件。

数据范围

对于所有测试数据，满足 $1 \le n,Q \le 1 \times 10^6, 1 \le a_i,v \le 10^9$

Hint: 由于本题输入规模可以达到 25MB，输出规模也可达到 5MB，请选手解题时注意 IO 优化。

也请选手注意一下程序自身的常数问题。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

关于本题的 Hack

由于造题时出题人构造的数据不够极端，本题设置了有点严格的时间限制，可能导致写标算的同学 TLE。因此本题暂时关闭 Hack 功能，对此 UOJ 管理员深表歉意。

下载

样例数据下载