Minh và Bảo đang đi du lịch tại nước Pháp. Ở đây có ~n~ thành phố, tất cả nằm dọc theo một con đường cao tốc. Các thành phố được đánh số liên tiếp bắt đầu từ ~1~ đến ~n~. Khoảng cách từ thành phố thứ ~i~ đến vị trí bắt đầu con đường cao tốc (~d_0 = 0~) là ~d_i~ (~i = 1, 2, \ldots, n~).

Minh đang ở thành phố ~x~, Bảo ở thành phố ~y~ (~1 \le x, y \le n~). Hai bạn muốn tìm một thành phố ~z~ để gặp nhau sao cho ~\max\{|d_x - d_z|, |d_y - d_z|\}~ là nhỏ nhất.

Yêu cầu: Cho ~d_1, d_2, \ldots, d_n~ và ~x, y~. Hãy tìm giá trị nhỏ nhất của ~\max\{|d_x - d_z|, |d_y - d_z|\}~.

Dữ liệu

Đọc từ tệp văn bản TRAVEL.INP có dạng:

• Dòng đầu chứa 2 số nguyên ~n, Q~ (~2 \le n, Q \le 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, \ldots, d_n~ (~d_1, d_2, \ldots, d_n \le 10^9~);
• ~Q~ dòng sau, mỗi dòng chứa 2 số ~x, y~ mô tả cho một câu hỏi (~1 \le x, y \le n~).

Các số trên một dòng được viết cách nhau bởi một dấu cách.

Kết quả

Ghi ra tệp văn bản TRAVEL.OUT gồm ~Q~ dòng. Mỗi dòng là giá trị ~\max\{|d_x - d_z|, |d_y - d_z|\}~ nhỏ nhất tìm được, tương ứng với một câu hỏi theo thứ tự trong tệp dữ liệu vào.

Ví dụ 1

Input

5 2
1 2 3 4 5
1 5
2 3

Output

2
1

Ví dụ 2

Input

5 2
15 28 48 56 100
1 5
2 4

Output

44
20

Giới hạn

• Có 40% số test tương ứng với 40% số điểm có ~n, Q \le 100~;
• Có 30% số test tương ứng với 30% số điểm có ~n, Q \le 10^5~ và ~d_1 < d_2 < \ldots < d_n~;
• Có 30% số test tương ứng với 30% số điểm có ~n, Q \le 10^5~.