An là một học sinh rất yêu thích môn Tin học, đặc biệt là lập trình. Để giúp con chuẩn bị cho kỳ thi Tin học trẻ tỉnh Bà Rịa-Vũng Tàu, Bố của bạn An đã đưa ra cho An bài toán để luyện tập kỹ năng lập trình như sau:

Cho dãy số nguyên dương gồm \(n\) phần tử \(a_{1},\ a_{2},\ ...,\ a_{n}\).

Yêu cầu: Cho \(t\) câu hỏi, với mỗi câu hỏi cung cấp cặp 2 số \(x_{i},\ y_{i}\ (1\ \leq \ x_{i}\ < \ y_{i}\ \leq \ n)\) và yêu cầu cho biết độ chênh lệch lớn nhất của 2 số bất kì có trong các phần tử liên tiếp nhau của dãy số từ phần tử ở vị trí \(x_{i}\) đến phần tử ở vị trí \(y_{i}\). Hãy cùng bạn An giải bài toán này!

Dữ liệu vào:

+ Dòng thứ nhất chứa số nguyên dương \(n\ (1\ < \ n\ \leq \ 10^{5})\);

+ Dòng thứ 2 chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ ...,\ a_{n}\ (a_{i}\ \leq \ 10^{9};\) với \(i\ = \ 1,\ 2,\ ...,\ n)\);

+ Dòng thứ 3 chứa giá trị \(t\);

+ Dòng thứ \(i\) trong \(t\) dòng tiếp theo chứa 2 số \(x_{i},\ y_{i}\ (i\ = \ 1,\ 2,\ ...,\ t)\).

Kết quả:

+ Ghi \(t\) dòng, dòng thứ \(i\) chứa một số nguyên duy nhất là đáp án của câu hỏi thứ \(i\).

Ví dụ:

Giải thích:

• Đoạn từ \(a_{1}\) đến \(a_{4}\) có độ chênh lệch lớn nhất là \(a_{4}\ –\ a_{1}\ = \ 6\ –\ 1\ = \ 5;\)

• Đoạn từ \(a_{2}\) đến \(a_{5}\) có độ chênh lệch lớn nhất là \(a_{4}\ –\ a_{2}\ = \ 6\ –\ 3\ = \ 3;\)

• Đoạn từ \(a_{5}\) đến \(a_{7}\) có độ chênh lệch lớn nhất là \(a_{6}\ –\ a_{5}\ = \ 8\ –\ 3\ = \ 5;\)

Ràng buộc dữ liệu:

+ 20% tests ứng với 20% số điểm ứng với \(t\ = \ 1\);

+ 80%\(\ \)tests còn lại ứng với 80% số điểm không ràng buộc gì thêm.