Balanced Lineup

Time limit1sMemory limit128 MB

Summary

Given N cow heights and Q ranges, report the difference between the maximum and minimum height within each query range.

Level: Medium6 of 10
Topics: Segment tree, Array, Implementation, Prefix sum
Solved: No attempts yet

Problem

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.

Input

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.

Output

$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.

Examples3

Example 1
Input
```
6 3
1
7
3
4
2
5
1 5
4 6
2 2
```
Expected output
```
6
3
0
```
Example 2
Input
```
1 1
42
1 1
```
Expected output
```
0
```
Example 3
Input
```
2 3
5
10
1 1
2 2
1 2
```
Expected output
```
0
0
5
```