F. First and Second Minimum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$a_1,a_2,\dots,a_n$$$ of $$$1,2,\dots,n$$$.

For $$$1\le x \lt y\le n$$$, the subarray $$$[x,y]$$$ is called special if the values at its two endpoints are exactly the smallest and the second smallest values in the subarray. In other words, the unordered pair $$$\{a_x,a_y\}$$$ must consist of the two smallest values among $$$a_x,a_{x+1},\dots,a_y$$$.

Every subarray of length $$$2$$$ is special.

For each query interval $$$[l,r]$$$, among all special subarrays $$$[x,y]$$$ satisfying $$$l\le x \lt y\le r$$$, determine the maximum length $$$y-x+1$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2\le n\le3\times10^5$$$, $$$1\le q\le3\times10^5$$$), denoting the length of the permutation and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, which form a permutation of $$$1,2,\dots,n$$$.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\le l \lt r\le n$$$), denoting a query interval.

Output

Print $$$q$$$ lines. The $$$i$$$-th line must contain one integer: the maximum length of a special subarray completely contained in the $$$i$$$-th query interval.

Example
Input
5 6
1 5 4 3 2
1 5
1 4
1 3
2 5
2 4
3 5
Output
5
4
3
2
2
2
Note

For the query $$$[1,5]$$$, the whole subarray is special because its endpoint values are $$$1$$$ and $$$2$$$, the two smallest values in the subarray. Therefore, the answer is $$$5$$$.

For the query $$$[1,4]$$$, the whole subarray is also special because its endpoint values are $$$1$$$ and $$$3$$$, so the answer is $$$4$$$. For the query $$$[1,3]$$$, the answer is $$$3$$$. For each remaining query, no special subarray of length greater than $$$2$$$ is fully contained in the query interval.