Du lịch

Minh và Bảo đang 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 từ 1 đến \(n\). Khoảng cách từ thành phố \(i\) đến vị trí bắt đầu con đường là \(D_i\).

Minh đang ở thành phố \(u\), Bảo ở thành phố \(v\). Hai bạn muốn tìm một thành phố \(k\) để gặp nhau sao cho
\begincenter
\(max(|D_k - D_u|,|D_k - D_v|)\)
\endcenter
là nhỏ nhất.

Yêu cầu: Cho \(n\) và \(q\) hãy tìm giá trị nhỏ nhất như yêu cầu ở trên.

Input

• Dòng đầu tiên chứa lần lượt hai số nguyên dương \(n, q\);
• Dòng thứ hai chứa dãy \(D_1, D_2, \dots, D_n\) \((1 \leq D_i \leq 10^9)\);
• Dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) mô tả một câu hỏi.

Output

Ghi ra \(q\) dòng lần lượt là đáp án cho \(q\) câu hỏi.

Example

5 2
1 2 3 4 5
1 5
2 3

2
1

Scoring

• Subtask \(1\) (\(40\%\) số điểm) : \(n, q \leq 10^2\).
• Subtask \(2\) (\(30\%\) số điểm) : \(n, q \leq 10^5\) và $d_1 < d_2 < \cdots < d_n $.
• Subtask \(2\) (\(30\%\) số điểm) : \(n, q \leq 10^5\).