$N$ bò Farmer John ($1 \le N \le 50,000$) xếp như nhau mỗi ngày vắt sữa. Một ngày chơi ultimate frisbee với vài con. Cho đơn giản chọn đoạn liên tiếp, nhưng chiều cao không quá khác để tất cả vui.

$Q$ ($1 \le Q \le 200,000$) nhóm có thể và chiều cao ($1 \le height \le 1,000,000$): tìm chênh cao nhất-thấp nhất mỗi nhóm.

Dữ liệu vào

Đọc đầu vào chuẩn.

Dòng 1: nguyên $N$, $Q$ cách dấu cách.

Dòng $2..N+1$: dòng $i+1$ chứa chiều cao của bò $i$ dưới dạng một số nguyên.

Dòng $N+2$..$N+Q+1$: nguyên $A$, $B$ ($1 \le A \le B \le N$), đoạn $A$ đến $B$ gồm hai đầu.

Dữ liệu ra

Ghi đầu ra chuẩn.

Dòng $1..Q$: nguyên mỗi trả lời, chênh cao nhất-thấp nhất trong đoạn.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6
3
0

Nguồn: USACO tháng 1 năm 2007, bạc