Description

我们定义“几乎递增”序列表示这个序列没有 $3$ 个连续的元素 $x,y,z$ 使得 $x\ge y\ge z$。

现在有一个长度为 $n$ 的序列，有 $q$ 次询问，每次问一个区间 $[l,r]$，你回答 $[l,r]$ 中最长的“几乎递增”子序列长度。

Input

一行两个正整数 $n,q$ 表示长度和查询个数。

Output

$q$ 行每行 $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

3
4
3
1
4
2
7
1

Note

In the first query, the subarray is $a_1, a_2, a_3 = [1,2,4]$. The whole subarray is almost-increasing, so the answer is $3$.

In the second query, the subarray is $a_1, a_2, a_3,a_4 = [1,2,4,3]$. The whole subarray is a almost-increasing, because there are no three consecutive elements such that $x \geq y \geq z$. So the answer is $4$.

In the third query, the subarray is $a_2, a_3, a_4, a_5 = [2, 4, 3, 3]$. The whole subarray is not almost-increasing, because the last three elements satisfy $4 \geq 3 \geq 3$. An almost-increasing subsequence of length $3$ can be found (for example taking $a_2,a_3,a_5 = [2,4,3]$ ). So the answer is $3$.