Hàng ngày khi lấy sữa, con bò của bác John luôn xếp hàng theo thứ tự không đổi được đánh số từ đến . 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 đã đo chiều cao của từng con bòn, con bò thứ có chiều cao là (nanomet) và chuẩn bị một danh sách gồm đoạn các con bò liên tiếp. 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 trong đoạn đó. 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 chứa hai số nguyên dương và ;
Dòng thứ hai chứa số nguyên dương ;
dòng tiếp theo, dòng thứ chứa hai số nguyên là đoạn các con bò thứ .
Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra:
Ghi trên một dòng số nguyên, số thứ là chênh lệch chiều cao lớn nhất của các con bò trong đoạn đến .
