Cho một dãy số gồm ~N~ số nguyên dương ~A_1,A_2,\ \ldots\ A_n~. Với một cặp số ~(u,v)~ bạn hãy tìm độ chênh lệch bé nhất khi chia đoạn con ~[A_u..A_v]~ thành hai phần.

Input:

Vào từ file văn bản "CHENHLECH.INP":

• Dòng đầu tiên là hai số nguyên dương ~N,\ Q\ (1\ \le\ N,\ Q\ \le\ 10^5)~. ~Q~ là số lượng truy vấn.
• Dòng tiếp theo là ~N~ số nguyên dương trong dãy ~A\ (A_i\ \ \le\ 10^9)~.
• ~Q~ dòng tiếp theo mỗi dòng là ~2~ số nguyên dương ~(u,v)~. Mỗi cặp số là một truy vấn cần bạn trả lời.

Output:

Ghi ra file văn bản "CHENHLECH.OUT":

• Gồm ~Q~ dòng, dòng thứ ~i~ là giá trị chênh lệch nhỏ nhất tìm được ứng với truy vấn ~i~.

Sample Input 1

5 1
3 1 4 2 5
2 5

Sample Output 1

2

Giải thích

• Với cặp ~(2,5)~ bạn cần tìm chênh lệch nhỏ nhất khi chia đoạn này ra hai phần. Ví dụ có các cách chia sau: ~(1)~ và ~(4,2,5)~; ~(1,4)~ và ~(2,5)~; ~(1,4,2)~ và ~(5)~; ~(1,4,2,5)~ và ~()~; Khi đó chênh lệch bé nhất là ~2~ – Tương ứng với cặp ~(1,4)\ (2,5)~.