Một Trung tâm Ngoại ngữ có tổ chức lớp học trực tuyến (online), trong đó có \(n\) tiết học (từ \(1\) đến \(n\)), tiết học thứ \(i\) có thời lượng \(a_i\) (tính bằng giây). Học viên có thể đăng ký học liên tiếp nhiều tiết học. Hãy tìm số lượng tiết học liên tiếp tối đa mà một học viên có thể tham gia trong một khoảng thời gian không vượt quá thời gian rảnh của họ.

Yêu cầu: Có \(q\) truy vấn, mỗi truy vấn cho biết thời gian rảnh của học viên là \(t\) giây. Với mỗi truy vấn, bạn cần tìm số lượng tiết học liên tiếp nhiều nhất mà học viên có thể tham gia trong thời gian không quá \(t\) giây.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^4\)) là số lượng tiết học.
• Dòng thứ hai chứa \(n\) số nguyên (cách nhau \(1\) dấu cách) \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^4\)) là thời lượng của từng tiết.
• Dòng thứ ba chứa số nguyên \(q\) (\(1 \le q \le 10^4\)) là số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(t\) (\(1 \le t \le 10^8\)) là thời gian rảnh của học viên.

Output

• Với mỗi truy vấn, in ra số lượng tiết học liên tiếp nhiều nhất mà học viên có thể tham gia trong thời gian \(t\) giây. Lưu ý học viên không bắt buộc phải tham gia từ tiết \(1\).

Example

5
4 2 3 1 5
3
7
10
15

3
4
5

Scoring

• Có \(40\%\) số điểm tương ứng với \(10 < n, q \le 5 \cdot 10^2\).
• Có \(30\%\) số điểm tương ứng với \(5 \cdot 10^2 < n, q \le 10^3\).
• Có \(30\%\) số điểm tương ứng với \(10^3 < n, q \le 10^4\).