Cho dãy \(A\) gồm có \(n\) phần tử: \(A_1, A_2, \dots, A_n\).
Gọi \(f(l) = \sum\limits_{i=1}^l A_i + \max\limits_{i=1}^l A_i\), tức là tổng của \(l\) phần tử đầu tiên cộng cho phần tử lớn nhất trong số \(l\) phần tử đầu tiên. Mặc định \(f(0) = 0\).

Hãy trả lời \(q\) câu hỏi có dạng: tìm \(l\) lớn nhất sao cho \(f(l) \leq X\).

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(n\) \((n \leq 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) \((A_i \leq 10^9)\).
• Dòng thứ ba chứa số \(q\) \((q \leq 10^5)\).
• \(q\) dòng tiếp theo, dòng thứ \(i\) chứa số \(X_i\) \((X_i \leq 10^{18})\), biểu thị cho câu hỏi: tìm \(l\) lớn nhất sao cho \(f(l) \leq X_i\).

Định dạng đầu ra

• In ra \(q\) dòng, dòng thứ \(i\) là đáp án cho câu hỏi thứ \(i\).

Điểm số

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 1000\)
• Subtask \(2\) (\(10\%\) số điểm): \(A_i = A_1\) với mọi \(i\).
• Subtask \(3\) (\(15\%\) số điểm): \(A_i \geq A_{i+1}\) với mọi \(i < n\).
• Subtask \(4\) (\(20\%\) số điểm): \(A_i \leq A_{i+1}\) với mọi \(i < n\).
• Subtask \(5\) (\(25\%\) số điểm): không có giới hạn nào khác.

Ví dụ

5
2 1 3 5 4
1
7

2

5
2 1 3 5 4
2
10
7

3
2