P17197 [KOI 2026 #2] 删除局部最小值

给定一个由互不相同的整数组成、长度为 $N$ 的序列 $A=[A_1,A_2,\cdots,A_N]$。 对于序列 $B$，将以下过程称为一次变换： - 设 $B=[B_1,B_2,\cdots,B_K]$。对于每个满足 $B_{i-1}>B_i

第一行依次给出两个以空格分隔的整数 $N$ 和 $Q$。 第二行依次给出 $N$ 个以空格分隔的整数 $A_1,A_2,\cdots,A_N$。 接下来的 $Q$ 行给出 $Q$ 个询问的信息。每行依次给出三个以空格分隔的整数 $l,r,t$，表示一个询问。

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

### 限制条件 - 给出的所有数均为整数。 - $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