Maximum Distance Between Seashells in Range

You are given a list of positions on a number line, representing the locations of seashells. You are also given several queries. Each query is specified by two integers \(l\) and \(r\) (1-indexed) and represents a subarray of the positions list, from the \(l^{th}\) to the \(r^{th}\) seashell.

Your task is to compute the maximum distance between any two seashells within each query range. Formally, for a given range, if \(P\) is the set of positions in that range, then the answer is given by:

\(\max(P) - \min(P)\)

Input is read from standard input and the result for each query should be printed to standard output on a new line.

inputFormat

The first line contains two integers \(n\) and \(q\), where \(n\) is the number of seashells, and \(q\) is the number of queries.

The second line contains \(n\) space-separated integers representing the positions of the seashells on the number line.

Each of the next \(q\) lines contains two space-separated integers \(l\) and \(r\) (1-indexed) describing a query.

outputFormat

For each query, print a single integer on a new line representing the maximum distance between any two seashells in the given query range.

## sample

5 3
1 3 7 9 10
1 3
2 4
1 5

6
6
9

</p>