Khoảng hạng của giá trị

Bối cảnh

Một kho điểm số được chuẩn hóa bằng cách sort tăng dần. Với mỗi giá trị x, bộ phận thống kê muốn biết toàn bộ khoảng rank mà x chiếm trong dãy đã sort: rank đầu tiên, rank cuối cùng và số lần xuất hiện. Ví dụ nếu dãy có ba số 8 liên tiếp ở các rank 5,6,7 thì query 8 phải trả 5 7 3, không chỉ YES/NO.

Bài Medium yêu cầu hai boundary search khác nhau trên cùng dữ liệu: first occurrence và last occurrence. Cần đặc biệt chú ý duplicate, not-found và chuyển đổi index 0-based trong code sang rank 1-based trong output. Sort chỉ thực hiện một lần; mỗi query sau đó phải O(log n), không được quét tuyến tính qua block duplicate.

Trong các bảng điểm thật, duplicate xuất hiện rất thường xuyên nên boundary search quan trọng hơn membership. Khi x xuất hiện nhiều lần, first rank và last rank còn có thể dùng để suy ra tỷ lệ, percentile hoặc vị trí chèn ổn định ở các bước sau. Vì vậy bài cố ý yêu cầu ba thông tin cùng lúc để người học thấy một binary search "tìm thấy x" chưa đủ; cần tiếp tục tìm đúng biên của block duplicate.

Yêu cầu

1. Sort dữ liệu tăng dần.
2. Với mỗi x, tìm first và last occurrence bằng binary search.
3. Nếu không có, in -1 -1 0.
4. Nếu có, in firstRank lastRank count theo rank 1-based.

Input

Dòng 1 n; dòng 2 n số; dòng 3 q; q dòng x.

Output

q dòng kết quả.

Ràng buộc

1≤n,q≤5000.

Ví dụ 1

Input

8
5 1 5 2 5 2 3 5
4
5
2
4
1

Output

5 8 4
2 3 2
-1 -1 0
1 1 1

Giải thích

Sau sort, dãy thành 1 2 2 3 5 5 5 5. Với x=5, first index là 4 và last index là 7, tương ứng rank 5..8, count 4. x=2 chiếm rank 2..3, count 2. x=4 không tồn tại nên -1 -1 0; x=1 ở rank 1 duy nhất. Các dòng output lần lượt phản ánh đúng các khoảng này.

Ví dụ 2

Input

1
7
2
7
8

Output

1 1 1
-1 -1 0

Giải thích

Dãy chỉ có 7. Query 7 có first=last=index0 nên rank 1 1 và count 1. Query 8 không có; cả hai boundary search đều không ghi nhận ans, vì vậy output là -1 -1 0.

Thông tin học tập

• Module: M05
• Buổi: B16
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: sort, binary search, first occurrence, last occurrence, rank interval, duplicates
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100