Ultimate Frisbee

Farmer John's cows line up every day for milking. One day, he decides to organize a game of Ultimate Frisbee by selecting a contiguous group of cows from the lineup. However, to ensure that everyone has fun, the height difference within the chosen group should not be too large.

You are given an array of cow heights \(h_1, h_2, \dots, h_n\) with \(1 \leq n \leq 5 \times 10^4\) and \(1 \leq h_i \leq 10^6\). Farmer John has prepared \(q\) queries (\(1 \leq q \leq 1.8 \times 10^5\)). In each query, you are given two integers \(a\) and \(b\) (with \(1 \leq a \leq b \leq n\)) representing a contiguous group of cows in the lineup. Your task is to output the difference between the tallest and the shortest cow in that group, i.e. \(\max\{h_a, \dots, h_b\} - \min\{h_a, \dots, h_b\}\).

inputFormat

The first line contains two integers \(n\) and \(q\): the number of cows and the number of queries.

The second line contains \(n\) space-separated integers representing the heights of the cows.

Each of the following \(q\) lines contains two integers \(a\) and \(b\) (with \(1 \leq a \leq b \leq n\)) representing a query.

outputFormat

For each query, output a single line containing the difference between the tallest and the shortest cow in the queried range.

sample

6 3
1 7 3 4 2 5
1 6
2 4
3 3

6
4
0