Sort rồi tra cứu

Bối cảnh

Một batch dữ liệu không có thứ tự nhưng cần trả lời nhiều query first-position sau khi chuẩn hóa tăng dần.

Bài tập kiểm tra pipeline đúng: đọc → sort → search.

Yêu cầu

1. Sort tăng dần.
2. Với mỗi x, tìm first occurrence 0-based bằng binary search.
3. Không có in -1.

Input

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

Output

q dòng index.

Ràng buộc

1≤n,q≤5000.

Ví dụ 1

Input

6
5 1 5 2 1 3
4
1
5
4
3

Output

0
4
-1
3

Giải thích

Dữ liệu 5 1 5 2 1 3 sau sort thành 1 1 2 3 5 5. Boundary search cho first(1)=0 và first(5)=4; giá trị 4 không tồn tại nên trả -1; first(3)=3. Vì đề hỏi vị trí đầu tiên trong state đã sort, output lần lượt là 0,4,-1,3.

Ví dụ 2

Input

1
7
2
7
8

Output

0
-1

Giải thích

Dãy chỉ có một phần tử 7; sau sort vẫn là [7]. Query 7 gặp đúng phần tử tại index 0, nên first occurrence bằng 0. Query 8 không tồn tại: boundary search thu hẹp đoạn rồi kết thúc với ans=-1. Vì output dùng index 0-based của state đã sort, hai dòng kết quả lần lượt là 0 và -1.

Thông tin học tập

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