#### BUBT vs MR. Array

**Author: ** Abu Rayhan Ahmad

Problem Setter:Jisan Sheikh, Dept. Of CSEBangabandhu 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

###### Input

###### Output

Language | Time | Memory |

GNU C 11 | 1s | 1024MB |

GNU C++ 14 | 1s | 1024MB |

GNU C++ 11 | 1s | 512MB |