Problem Setter: Jisan Sheikh, Dept. Of CSE

Bangabandhu Sheikh Mujibur Rahman Science & Technology University (BSMRSTU).

You are the best programmer of BUBT. Now you are assigned to save the dignity of BUBT to

the fact that MR. Array challenged BUBT with a problem. As you are the best programmer and it is the question of dignity it’s your duty save the dignity of BUBT.

Okay now let me describe the challenge.

You are going to have an array and some query.

For each query you have to find the size of minimum sub array in the range l, r where difference

of biggest element and smallest is maximum.

Can you save the dignity of BUBT?.

Input Format

Input starts with two integer N and Q (1 <= N, Q <= 100000).

N integers in the next line denoting the elements of the array. (1 <= Ai <= 10^9 and all the elements are distinct).

Next Q lines describing the query each of them containing l and r (1 <= l <= r <= N).

Output Format

For each query print an integer (Size of the minimum sub array in the given range

where difference of the biggest element and smallest element is maximum).

Samples