Cho ~N~ điểm nên trục ~Ox~ có tọa độ ~A_1, A_2, ..., A_N~.

Thực hiện ~Q~ truy vấn, mỗi truy vấn bao gồm hai số nguyên ~B~ và ~K~, gọi ~A_x~ ~(1 \le x \le N)~ là điểm gần thứ ~K~ so với điểm ~B~, yêu cầu xác định giá trị ~|B-A_x|~.

Lưu ý rằng nếu tồn tại hai điểm ~A_i~ và ~A_j~ ~(i \neq j)~ có cùng khoảng cách đến điểm ~B~ thì hai điểm này vẫn được xét ở hai vị thứ khác nhau.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_i~ ~(- 10^8 \le A_i \le 10^8)~.
• Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le N \le 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~B~ và ~K~ mô tả truy vấn ~(- 10^8 \le B \le 10^8~ ; ~1 \le K \le N)~.

Output

• Với mỗi truy vấn, in ra kết quả trên một dòng.

Examples

Sample Input

5
-5 -1 0 6 8
3
-2 3
0 1
7 2

Sample Output

3
0
1

Scoring

• Subtask ~1~ ~-~ ~500~ điểm: ~N,Q \le 1000~
• Subtask ~2~ ~-~ ~750~ điểm: ~K=1~ với mọi truy vấn
• Subtask ~3~ ~-~ ~750~ điểm: Không có ràng buộc gì thêm

Notes

Ở truy vấn thứ nhất, điểm gần thứ ba so với điểm ~B=-2~ là điểm ~A_1=-5~, vì vậy ~|B-A_3|=|(-2)-(-5)|=3~.

Ở truy vấn thứ hai, điểm gần nhất so với điểm ~B=0~ là điểm ~A_3=0~, vì vậy ~|B-A_3|=|0-0|=2~.

Ở truy vấn thứ ba, hai điểm ~A_4=6~ và ~A_5=8~ có cùng khoảng cách đến điểm ~B=7~, nhưng hai điểm này vẫn được xem là điểm gần nhất và gần thứ hai so với điểm ~B~.