Khi vắt sữa hằng ngày, $N$ con bò của Farmer John ($1 \le N \le 50,000$) luôn xếp hàng theo cùng một thứ tự. Một ngày nọ, Farmer John quyết định tổ chức trò ultimate frisbee với một số con bò. Để đơn giản, ông sẽ chọn một đoạn liên tiếp các con bò trong hàng vắt sữa để tham gia. Tuy nhiên, để tất cả đều vui, chiều cao của chúng không nên chênh lệch quá nhiều.

Farmer John đã lập danh sách $Q$ ($1 \le Q \le 200,000$) nhóm bò có thể tham gia và chiều cao của chúng ($1 \le height \le 1,000,000$). Với mỗi nhóm, hãy giúp ông xác định chênh lệch chiều cao giữa con cao nhất và con thấp nhất trong nhóm.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

Dòng 1: hai số nguyên $N$ và $Q$, cách nhau bởi một dấu cách.

Các dòng $2 \ldots N+1$: dòng $i+1$ chứa một số nguyên là chiều cao của con bò $i$.

Các dòng $N+2 \ldots N+Q+1$: hai số nguyên $A$ và $B$ ($1 \le A \le B \le N$), biểu thị đoạn bò từ $A$ đến $B$, gồm cả hai đầu.

Dữ liệu ra

Ghi kết quả ra đầu ra chuẩn.

Các dòng $1 \ldots Q$: mỗi dòng chứa một số nguyên trả lời truy vấn tương ứng và biểu thị chênh lệch chiều cao giữa con bò cao nhất và thấp nhất trong đoạn.

Ví dụ

Dữ liệu vào 1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Dữ liệu ra 1

6
3
0

Nguồn bài toán: USACO, tháng 1 năm 2007, Gold