题目描述

题目译自 JOISC 2016 Day2 T1 「雇用計画」

JOI 社为了扩大业务而开始了新社员招募。社员有 $N$ 名候补者，编号从 $1$ 到 $N$，每名候补者有称为评价值的一个确定整数。评价值高于某一个值的候补者全部都将被聘用，他们还将分为几个组别。如果 $a, b$ $(a < b)$ 同时被聘用且 $c$ $(a \le c \le b)$ 全部被聘用时，$a,b$ 进入同一组。

你要处理 $M$ 个查询，查询有以下两种：

1. 评价值 $B_j$ 以上的候补者全部聘用时的组数；
2. 将候补者 $C_j$ 的评价值更新为 $D_j$。

---

输入格式

• 第一行两个整数 $N, M$；
• 接下来 $N$ 行第 $i$ 行给出候补者评价值的初始值 $A_i$；
• 接下来 $M$ 行中，第 $j$ 行有一个整数 $T_j$：
  • $T_j = 1$ 时给出 $B_j$，意义如上；
  • $T_j = 2$ 时给出 $C_j, D_j$，意义如上。

---

输出格式

每行一个整数表示分组个数。

---

样例 1

输入

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

输出

2
1
2

解释：

• 第一次查询时，候补者 $1,2,4$ 被聘用，$1,2$ 一组，$4$ 为一组，输出 $2$；
• 第二次查询将候补者 $4$ 的评价值更新为 $1$；
• 第三次查询时，候补者 $1,2$ 为一组，输出 $1$；
• 第四次查询时候补者 $1,2,3$ 一组，$5$ 一组，输出 $2$。

---

样例 2

输入

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

输出

0
1
3
3
2

---

样例 3

输入

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

输出

2
1
0

---

数据范围与提示

对于全部数据：

• $1 \le N,M \le 2\times 10^5$
• $1 \le A_i,B_j,D_j \le 10^9$
• $1 \le T_j \le 2$
• $1 \le C_j \le N$

并保证至少有一次查询 $T_j=1$。

具体子任务限制及得分情况如下表：

Subtask	限制	分数
1	$N,M \le 2000$	10
2	$T_j = 1$	30
3	无追加限制	60

---