如果一个序列不包含三个连续元素 $$$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$$$。
输出
对于每个 $$$q$$$ 查询,打印一行,其中包含子数组 $$$a_l, a_{l+1}, \dots, a_r$$$ 的最长几乎递增子序列的长度。
示例
输入 #1
9 8 1 2 4 3 3 5 6 2 1 1 3 1 4 2 5 6 6 3 7 7 8 1 8 8 8
输出 #1
3 4 3 1 4 2 7 1
注意
在第一个查询中,子数组为 $$$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$$$。