Tra cứu bảng xếp hạng

Bối cảnh

Một bảng điểm xếp hạng theo score giảm dần. Nếu một score xuất hiện nhiều lần, truy vấn cần rank đầu tiên của score đó.

Workshop phân biệt membership với boundary search và xử lý duplicate.

Yêu cầu

1. Sort score giảm dần.
2. Với mỗi query x, tìm vị trí đầu tiên có score=x bằng binary search.
3. In rank 1-based hoặc NOT_FOUND.

Yêu cầu tổ chức code

Workshop phải thể hiện sort + binary boundary search, không dùng linear scan cho toàn bộ query.

Online Judge chấm output. Với bài nhạy về cấu trúc lời giải, giảng viên có thể review source code để xác nhận học viên luyện đúng năng lực.

Input

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

Output

q dòng rank hoặc NOT_FOUND.

Ràng buộc

1≤n,q≤5000.

Ví dụ 1

Input

6
80 95 70 95 90 80
5
95
80
70
100
90

Output

1
4
6
NOT_FOUND
3

Giải thích

Sau sort giảm dần, bảng điểm là 95 95 90 80 80 70. Với score 95, vị trí đầu tiên nằm ở rank 1; score 80 xuất hiện hai lần nhưng boundary search phải trả rank đầu là 4. Score 70 ở rank 6, còn 100 không có. Query 90 trả rank 3. Kết quả cho thấy bài không chỉ kiểm tra membership mà kiểm tra first occurrence trong dữ liệu có duplicate.

Ví dụ 2

Input

1
50
2
50
40

Output

1
NOT_FOUND

Giải thích

Chỉ có score 50 nên rank đầu của 50 là 1. Query 40 không tồn tại; binary search phải kết thúc với ans=-1 và in NOT_FOUND, thay vì trả một vị trí chèn. Đây là case nhỏ để kiểm tra logic not-found.

Thông tin học tập

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