Nguồn: http://vn.spoj.com
Hàng ngày khi lấy sữa, N con bò của bác John (1 ≤ N ≤ 50000) luôn
xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò
chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các
con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò
phải không quá chênh lệch về chiều cao.
Bác John đã chuẩn bị một danh sách gồm Q (1 ≤
Q ≤ 200000) đoạn các con bò và chiều cao của chúng (trong phạm vi [1,
1000000]). Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữa con
bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này!
Dữ liệu vào:
+ Dòng đầu tiên chứa 2 số
nguyên N và Q.
+ Dòng thứ i trong số N
dòng sau chứa 1 số nguyên duy nhất, là độ cao của con bò thứ i.
+ Dòng thứ i trong số Q
trong tiếp theo chứa 2 số nguyên A, B (1 ≤ A ≤ B ≤ N), cho biết đoạn các con bò
từ A đến B.
Dữ liệu ra:
Gồm Q dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao
giữa con bò thấp nhất và cao nhất thuộc đoạn tương ứng.
Ví dụ:
|
Input
|
Output
|
6 3
1
7
3
4
2
5
1 5
4 6
2 2
|
6
3
0
|
