KEOCO Thi kéo co

Hội trại xuân của trường LTV sắp diễn ra. Vì thế, thầy chủ nhiệm lớp chuyên Tin muốn chọn ra một đội thi kéo co. Theo kinh nghiệm của thầy, các học sinh trong đội kéo co nên có sức mạnh đồng đều nhau, càng ít chênh lệnh càng tốt.

            Để chọn lựa, Thầy xếp N học sinh được đánh số thứ tự từ 1 đến N thành một hàng ngang. Học sinh thứ i có sức mạnh a_i. Thầy sẽ chọn ra một đoạn liên tiếp các học sinh lập đội. Hiện thầy đã có M đoạn học sinh. Hãy giúp thầy tính độ chênh lệch sức mạnh giữa học sinh khỏe nhất và yếu nhất trong từng đoạn để thầy dễ dàng chọn lựa.

Dữ liệu

• Dòng đầu tiên chứa 2 số nguyên N và M.(1 ≤ N ≤ 50000) (1 ≤ M ≤ 200000)
• Dòng thứ i trong số N dòng sau chứa 1 số nguyên duy nhất, là sức mạnh của học sinh thứ i.(trong phạm vi [1, 1000000]).
• Dòng thứ i trong số M trong tiếp theo chứa 2 số nguyên A, B (1 ≤ A ≤ B ≤ N), cho biết đoạn các học sinh từ A đến B.

Kết qủa: Gồm M dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch sức mạnh giữa học sinh khỏe nhất và yếu nhất thuộc đoạn tương ứng.

Input	Output
6 3 1 7 3 4 2 5 1 5 4 6 2 2	6 3 0