Các bài tập về dãy số rất hay và thường xuyên gặp trong các kỳ thi. Hôm nay bài tập thử thách cho các bạn là tìm độ chênh lệch như sau:

Cho một dãy số gồm N số nguyên dương A₁, A₂, … 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.

Bạn hãy xem ví dụ:

+ Cho dãy A: 3 1 4 2 5

+ Với cặp (u,v) = (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).

Input: 

+ Dòng đầu tiên là hai số nguyên dương N, Q (1 ≤ N, K ≤ 10⁵). 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 ≤ 10⁹; i = 1, 2, …, n).

+ 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: 

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.