题目描述

给你一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ 。

请按照给出的顺序处理 $Q$ 个查询。每个查询属于以下两种类型之一：

• 1 p x：将 $A_p$ 的值改为 $x$ 。
• 2 l r：打印 $(A_l, A_{l+1}, \ldots, A_r)$ 中第二大数值的出现次数。更准确地说，打印满足 $l \leq i \leq r$ 的整数 $i$ 的个数，即在 $A_l, A_{l+1}, \ldots, A_r$ 中，有一个不同的值大于 $A_i$ 。

输入格式

第一行包含 $2$ 个正整数 $N,Q$，表示数列长度和询问个数。保证 $1\le N,Q\le 2\times10^5$。
第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示初始数列。保证 $|A_i|\le 10^9$。
接下来 $q$ 行，每行一个操作，为以下两种之一：

• 1 p x：将 $A_p$ 的值改为 $x$；
• 2 l r：打印 $(A_l, A_{l+1}, \ldots, A_r)$ 中第二大数值的出现次数

输出格式

对于每个 2 l r 操作输出一行表示答案，如果没有第二大的数（比如：$A[l..r]$ 全相等），就输出 $0$

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

1
0
2

1 1
1000000000
2 1 1

0

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

0
1
0
2
4

提示

【样例 #1 解释】

数据规模与限制

• $1\le N,Q\le 2\times10^5$
• $|A_i|\le 10^9$
• $1\le l\le r\le n$

来源

• abc_343_F: Second Largest Query