Trạm gần truy vấn nhất

Bối cảnh

Trên một tuyến đường có n trạm đo tại các tọa độ nguyên, ban đầu được nhập không theo thứ tự. Với mỗi vị trí truy vấn x, hệ thống cần trả trạm gần x nhất theo khoảng cách tuyệt đối. Nếu có hai trạm cách x bằng nhau, phải chọn tọa độ nhỏ hơn để kết quả ổn định.

Sau khi sort vị trí trạm tăng dần, trạm gần x chỉ có thể nằm ngay tại vị trí chèn của x hoặc phần tử đứng trước vị trí chèn đó. Vì vậy không cần quét toàn bộ dãy. Bài Medium yêu cầu học viên chuyển từ "binary search tìm đúng x" sang "binary search tìm boundary rồi đánh giá các ứng viên lân cận", một mẫu rất thường gặp trong bài thi.

Hãy chú ý rằng query có thể nằm ngoài toàn bộ miền tọa độ, trùng đúng một trạm, hoặc nằm chính giữa hai trạm. Ba trường hợp này thường làm code binary search lỗi ở pos=0, pos=n hoặc tie. Vì thế bài không chỉ kiểm tra tốc độ O(log n) mà còn kiểm tra cách biến vị trí chèn thành một tập ứng viên nhỏ và xử lý biên an toàn.

Yêu cầu

1. Sort tọa độ tăng dần.
2. Với mỗi x, tìm vị trí đầu tiên a[pos] >= x.
3. So sánh tối đa hai ứng viên pos và pos-1.
4. Chọn khoảng cách nhỏ nhất; tie chọn tọa độ nhỏ hơn.
5. In station distance.

Input

Dòng 1 n; dòng 2 n tọa độ; dòng 3 q; q dòng x.

Output

q dòng station distance.

Ràng buộc

1≤n,q≤5000, tọa độ và query trong long long.

Ví dụ 1

Input

5
0 10 20 30 40
5
7
15
-3
50
20

Output

10 3
10 5
0 3
40 10
20 0

Giải thích

Với query 7, vị trí chèn nằm trước 10; hai ứng viên là 0 và 10, khoảng cách lần lượt 7 và 3 nên chọn 10. Query 15 cách 10 và 20 cùng 5, tie chọn tọa độ nhỏ hơn là 10. Query -3 chỉ có ứng viên phía phải 0; query 50 chỉ có phía trái 40; query 20 trùng trạm nên distance 0. Các output phản ánh đúng năm trường hợp.

Ví dụ 2

Input

1
100
3
99
100
101

Output

100 1
100 0
100 1

Giải thích

Chỉ có một trạm tại 100. Mọi query đều phải chọn trạm này: 99 cách 1, 100 cách 0, 101 cách 1. Binary search boundary có thể trả 0 hoặc n tùy query, nhưng logic ứng viên vẫn xử lý đúng n=1.

Thông tin học tập

• Module: M05
• Buổi: B16
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: sort, binary search, lower boundary, nearest value, tie-break
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100