Balanced Lineup

For the daily milking, Farmer John's $N$ cows ($1 \le N \le 50000$) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he takes a contiguous range of cows from the lineup to play. However, for all the cows to have fun, their heights should not differ too much.

Farmer John prepares $Q$ candidate groups ($1 \le Q \le 180000$) along with the cows' heights ($1 \le \text{height} \le 1000000$). For each group, determine the difference in height between the shortest and the tallest cow in that group.

Note: on the largest test case, I/O takes up the majority of the runtime.

• Line 1: Two space-separated integers, $N$ and $Q$.
• Lines 2 to $N+1$: Line $i+1$ contains a single integer, the height of cow $i$.
• Lines $N+2$ to $N+Q+1$: Two integers $A$ and $B$ ($1 \le A \le B \le N$), representing the range of cows from $A$ to $B$ inclusive.

• $Q$ lines: Each line contains a single integer, the answer to one query — the difference in height between the tallest and the shortest cow in the given range.