富金森林公园

题目描述

博艾的富金森林公园里有一个长长的富金山脉,山脉是由一块块巨石并列构成的,编号从 $1$ 到 $N$ 。每一个巨石有一个海拔高度。而这个山脉又在一个盆地中,盆地里可能会积水,积水也有一个海拔高度,所有**严格低于**这个海拔高度的巨石,就会在水面下隐藏。 由于地壳运动,巨石的海拔高度可能会随时变化,每次一块的巨石会变成新的海拔高度。当然,水面的高度也会随时发生变化。 因为有这样奇妙的地质奇观,吸引了很多游客来游玩。uim 作为一个游客,可以告诉你此时水位海拔,你得告诉他,能看到有几个连续露出水面的部分。(与水面持平我们也认为是露出)

输入输出格式

输入格式


第一行两个整数 $N$ 和 $M$,分别表示 $N$ 块石头,$M$ 个询问。 接下来一行,$N$ 个整数 $A_i$ 表示每个巨石的初始海拔。 接下来 $M$ 行,每行有两个或者三个数,每一行如果第一个数是 `1`,那么后面跟一个 $B_j$,表示水面海拔。如果第一个数是 `2`,后面跟两个整数,$C_j$ 和 $D_j$,表示编号 $C_j$ 的巨石海拔变为 $D_j$。

输出格式


对于每个 `1` 询问,给出一个整数答案,也就是露出了几部分的山峰。

输入输出样例

输入样例 #1

5 4
8 6 3 5 4
1 5
2 4 1
1 5
1 3

输出样例 #1

2
1
2

说明

$10\%$ 的数据,$N,M<=2000$。 另外 $30\%$ 的数据, 只有 `1` 的询问。 $100\%$ 的数据,$1<=N,M<=200000,1<=A_i,B_j,D_j<=10^9$,一定有 `1` 询问。