CF1817A Almost Increasing Subsequence

如果一个序列中不存在三个连续的元素 $x, y, z$ 满足 $x \ge y \ge z$，则称该序列为“几乎递增”序列。 给定一个数组 $a_1, a_2, \dots, a_n$ 和 $q$ 个查询。 每个查询包含两个整数 $1 \le l \le r \le n$。对于每个查询，求子数组 $a_l, a_{l+1}, \dots, a_r$ 的最长“几乎递增”子序列的长度。 子序列是指可以通过删除原序列中的零个或多个元素（不改变剩余元素的顺序）得到的序列。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 200\,000$），分别表示数组 $a$ 的长度和查询的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示一次查询，询问子数组 $a_l, a_{l+1}, \dots, a_r$。

对于每个查询，输出一行，表示子数组 $a_l, a_{l+1}, \dots, a_r$ 的最长“几乎递增”子序列的长度。

对于第一个查询，子数组为 $a_1, a_2, a_3 = [1,2,4]$。整个子数组本身就是“几乎递增”序列，因此答案为 $3$。 对于第二个查询，子数组为 $a_1, a_2, a_3, a_4 = [1,2,4,3]$。整个子数组本身也是“几乎递增”序列，因为不存在三个连续元素满足 $x \geq y \geq z$。因此答案为 $4$。 对于第三个查询，子数组为 $a_2, a_3, a_4, a_5 = [2, 4, 3, 3]$。整个子数组不是“几乎递增”序列，因为最后三个元素满足 $4 \geq 3 \geq 3$。可以找到一个长度为 $3$ 的“几乎递增”子序列（例如取 $a_2, a_3, a_5 = [2,4,3]$）。因此答案为 $3$。 由 ChatGPT 4.1 翻译