Gặp lại trên đường

Trên một xa lộ thẳng có \(N\) thị trấn đánh số từ \(1\) đến \(N\); thị trấn \(i\) cách điểm đầu đường \(d_i\) đơn vị (các giá trị \(d_i\) không nhất thiết đôi một khác nhau hay đã sắp xếp).

Có \(Q\) cặp bạn, mỗi cặp là hai người ở thị trấn \(x\) và \(y\). Họ muốn chọn một thị trấn \(z\) (có thể trùng với \(x\) hoặc \(y\)) làm nơi hẹn sao cho người phải đi xa hơn đi càng ít càng tốt, tức là giá trị

là nhỏ nhất. Với mỗi cặp, hãy in ra giá trị nhỏ nhất này.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên \(d_1, \dots, d_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\).

Output

In \(Q\) dòng, dòng thứ \(j\) là đáp án của cặp thứ \(j\).

Constraints

• \(1 \le N, Q \le 10^5\)
• \(1 \le d_i \le 10^9\)
• \(1 \le x, y \le N\)

Sample Input

6 3
2 9 4 15 7 11
1 4
3 3
2 5

Sample Output

7
0
2

Explanation

Cặp \((1, 4)\) ở vị trí \(2\) và \(15\): chọn \(z = 2\) (vị trí \(9\)) cho giá trị \(\max(7, 6) = 7\); chọn thị trấn \(5\) (vị trí \(7\)) cho \(\max(5, 8) = 8\). Đáp án là \(7\).