题目描述

给定一个由互不相同的整数组成、长度为 $N$ 的序列 $A=[A_1,A_2,\cdots,A_N]$。

对于序列 $B$，将以下过程称为一次变换：

• 设 $B=[B_1,B_2,\cdots,B_K]$。对于每个满足 $B_{i-1}>B_i<B_{i+1}$ 的整数 $i$（$2 \le i \le K-1$），将 $B_i$ 称为应删除的元素。将序列 $B$ 中所有应删除的元素同时删除，再保持剩余元素的相对顺序，将它们重新连接起来。

例如，对序列 $[5,1,3,2,4]$ 应用三次变换后，序列将如下变化：

$$[5,1,3,2,4]\to[5,3,4]\to[5,4]\to[5,4]$$

给定 $Q$ 个询问。每个询问由三个整数 $l,r,t$ 表示。对于每个询问 $(l,r,t)$，请输出对序列 $[A_l,A_{l+1},\cdots,A_r]$ 应用 $t$ 次变换后，序列中剩余元素的个数。

输入格式

第一行依次给出两个以空格分隔的整数 $N$ 和 $Q$。

第二行依次给出 $N$ 个以空格分隔的整数 $A_1,A_2,\cdots,A_N$。

接下来的 $Q$ 行给出 $Q$ 个询问的信息。每行依次给出三个以空格分隔的整数 $l,r,t$，表示一个询问。

输出格式

从第一行开始依次输出 $Q$ 行答案。按照输入给出的顺序，每个询问的答案单独输出一行。

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

3
2
3
3
2

15 7
14 5 2 7 11 13 3 12 9 4 10 8 1 6 15
1 15 1
1 15 2
1 15 3
1 15 4
1 15 5
1 15 6
1 15 7

11
8
6
4
3
2
2

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

8
6
2
3
5
3
4
3
2
3

提示

限制条件

• 给出的所有数均为整数。
• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• 序列 $A$ 是 $1,2,\cdots,N$ 的一个排列，即 $\{A_1,A_2,\cdots,A_N\}=\{1,2,\cdots,N\}$。
• 对于每个询问，$1 \le l \le r \le N$。
• 对于每个询问，$1 \le t \le N$。

子任务

1. （$6$ 分）$N \le 5\,000$；对于每个询问，$l=1$ 且 $r=N$。
2. （$11$ 分）对于每个询问，$l=1$ 且 $r=N$。
3. （$6$ 分）对于每个询问，$t=1$。
4. （$12$ 分）对于每个询问，$t=N$。
5. （$7$ 分）存在某个整数 $p$（$1 \le p \le N$），使以下条件同时成立：
   • 对于每个整数 $i$（$1 \le i \le p-1$），$A_i>A_{i+1}$。
   • 对于每个整数 $i$（$p \le i \le N-1$），$A_i<A_{i+1}$。
6. （$26$ 分）对序列 $A=[A_1,A_2,\cdots,A_N]$ 应用 $20$ 次变换后，再继续应用变换也不会使序列发生变化。
7. （$32$ 分）没有额外限制。

翻译由 ChatGPT-5.6 完成