Đủ điểm mục tiêu với ít người nhất

Bối cảnh

Một đội tuyển có n mức đóng góp không âm. Ban huấn luyện luôn chọn người theo đóng góp từ cao xuống thấp. Với mỗi mục tiêu S, cần biết số lượng ít nhất k người đứng đầu sao cho tổng đóng góp của top-k đạt ít nhất S. Nếu ngay cả tổng của cả đội vẫn nhỏ hơn S, in -1.

Sau khi sort giảm dần, prefix pre[k] là tổng top-k. Vì mọi score không âm, pre[k] không giảm theo k, nên với mỗi S có thể binary search vị trí đầu tiên pre[k] ≥ S. Bài Medium kết hợp ba mảnh kiến thức đã học: sort tạo ranking, prefix biến tổng top-k thành O(1), và binary search từ B16 tìm boundary trên prefix.

Trong một hệ thống tuyển chọn thực tế, nhiều truy vấn S có thể được gửi cho cùng một bảng điểm, nên việc tính lại tổng từ đầu cho từng S là lãng phí. Prefix biến ranking thành một "thang tích lũy"; boundary search chỉ cần tìm bậc đầu tiên đủ cao. Mô hình này tương tự các bài hỏi số lượng ít nhất tài nguyên cần để đạt quota, ngân sách hoặc công suất mục tiêu.

Yêu cầu

1. Sort score giảm dần.
2. Build prefix pre[0..n].
3. Với mỗi S, tìm k nhỏ nhất pre[k]≥S.
4. Nếu pre[n]<S, in -1.

Input

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

Output

q dòng k hoặc -1.

Ràng buộc

1≤n,q≤5000, 0≤score≤10^9, 0≤S≤10^18.

Ví dụ 1

Input

5
9 7 5 3 1
5
1
9
10
21
30

Output

1
1
2
3
-1

Giải thích

Ranking đã là 9 7 5 3 1, prefix 0,9,16,21,24,25. Mục tiêu 1 và 9 đều đạt với k=1; S=10 cần k=2 vì pre1=9<10 nhưng pre2=16≥10; S=21 cần k=3; S=30 vượt tổng 25 nên binary search không tìm được và in -1.

Ví dụ 2

Input

1
0
3
0
1
2

Output

0
-1
-1

Giải thích

Đội chỉ có một score 0, prefix là 0,0. Với S=0, vị trí đầu tiên thỏa pre[k]≥0 là k=0, nên output 0 — không cần chọn ai. Với S=1 hoặc 2, tổng cả đội vẫn 0 nên in -1.

Thông tin học tập

• Module: M05
• Buổi: B17
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: sort descending, prefix sum, binary search on prefix, minimum k
• Giới hạn kiến thức: B01-B17
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100