Đếm mức giá không vượt ngân sách

Bối cảnh và bài toán

Một danh mục có n mức giá. Trong nhiều ngày khác nhau, người dùng đưa ra một ngân sách m và muốn biết có bao nhiêu lựa chọn có giá không vượt quá ngân sách đó.

Yêu cầu

Với mỗi ngân sách, đếm số giá trị a[i] <= m.

Input

• Dòng 1: n.
• Dòng 2: n mức giá.
• Dòng 3: q.
• q dòng tiếp: ngân sách m.

Output

In số lựa chọn hợp lệ cho từng truy vấn.

Ràng buộc

• 1 <= n, q <= 10^5
• 1 <= a[i] <= 10^5
• 0 <= m <= 10^9

Chấm điểm

Ví dụ 1

Input

5
3 10 8 6 11
4
1
10
3
11

Output

0
4
1
5

Giải thích. Với ngân sách 10 có bốn mức giá 3,6,8,10; với 11 có cả năm.

Ví dụ 2

Input

5
1 1 1 1 1
2
0
1

Output

0
5

Giải thích. upper_bound phải đi qua toàn bộ các giá trị bằng m, không chỉ một phần tử.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 706B — Interesting Drink.

Tham khảo: https://codeforces.com/problemset/problem/706/B