Tèo có một dãy số liệu về độ cao của \(N\) ngọn núi. Cậu muốn biết sự chênh lệch giữa ngọn núi cao nhất và thấp nhất trong một khu vực từ \(l\) đến \(r\).

Hãy giúp Tèo tính hiệu số giữa giá trị lớn nhất và nhỏ nhất trên mỗi đoạn.

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra hiệu số tìm được trên một dòng.

Ví dụ

Input:

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

Output:

7
7
5