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 (điểm gốc) là ~d_i~ ~(i = 1, 2, …, n)~.

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

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

Input

Vào từ file văn bản TRAVEL.INP:

• Dòng đầu tiên chứa ~2~ số nguyên ~n, Q~ ~(2\leq n\leq 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2,..., d_n~ ~(d_1, d_2,..., d_n\leq 10^9)~.

• ~Q~ dòng sau, mỗi dòng chứa hai số ~x, y,~ mô tả cho một câu hỏi ~(1\leq x, y\leq n)~.

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

Output

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

Scoring

• Subtask ~1~ ~(40\%)~: ~n, Q\leq 100~.
• Subtask ~2~ ~(30\%)~: ~n, Q\leq 10^5~ và ~d_1<d_2<...<d_n~.</li>
• Subtask ~3~ ~(30\%)~: ~n, Q\leq 10^5~.

Example input 1

5 2
1 2 3 4 5
1 5
2 3

Example output 1

2
1

Example input 2

5 2
15 28 48 56 100
1 5
2 4

Example output 2

44
20