Có một chú tiểu trong một ngôi chùa TLT nọ. Mỗi buổi chiều, chú có một công việc là gánh nước từ con suối gần nhất về để mọi người trong chùa sử dụng.

Cụ thể, chú tiểu cần gánh đầy \(N ~ (1 \leq N \leq 2\times 10^5)\) gàu nước, gàu nước thứ \(i ~ (1 \leq i \leq N)\) có dung tích là \(A_i ~ (1 \leq A_i \leq 10^9)\) lít nước. Mỗi lần đi gánh nước, chú tiểu đưa hết \(N\) gàu nước theo. Mọi hôm, chú sẽ múc lần lượt từng gàu nước và gánh hết về. Nhưng hôm nay chú muốn thử chơi một trò chơi thú vị như sau.

Chú tiểu sẽ bố trí các gàu nước sao cho khi gàu nước thứ \(i ~ (1 \leq i < N)\) đã đầy và được đổ thêm nước, số nước dư thừa sẽ được đổ sang gàu nước thứ \(i + 1\) (nếu gàu thứ \(i+1\) cũng đầy thì lượng nước thừa kia sẽ tự động được đổ sang gàu \(i+2\) nếu \(i+2\leq N\) và cứ thế ...). Nếu gàu nước thứ \(N\) đã đầy và được đổ thêm nước thì lượng nước thừa sẽ đổ xuống đất. Một gàu nước được gọi là đầy khi mà lượng nước nó chứa đã bằng dung tích.

Vốn là một người có võ công lợi hại, cậu có thể dùng tay hất nước vào cả \(N\) gàu nước cùng một lần, coi như mỗi giây cậu có thể hất một lít nước vào các gàu. Nhưng tất nhiên hắt nước cả \(N\) gàu một lần rất mất sức, nên cậu muốn chọn ít gàu nước nhất để hất nước vào sao cho cả \(N\) gàu nước đều đầy trong thời gian cho phép, vì đi quá lâu chú tiểu sẽ bị phạt.

Yêu cầu: Cho \(Q\) câu hỏi, câu hỏi thứ \(i\) là để đổ đầy cả \(N\) gàu nước trong thời gian không quá \(v_i\) giây thì phải chọn ít nhất bao nhiêu gàu nước để hất nước vào, nếu không tồn tại phương án thỏa mãn yêu cầu thì đưa ra \(-1\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N ~ (1 \leq N \leq 2\times 10^5)\) là số gàu nước.
• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i ~ (1 \leq i \leq N)\) là \(A_i ~ (1 \leq A_i \leq 10^9)\).
• Dòng thứ ba chứa một số nguyên dương \(Q ~ (1 \leq Q \leq \min(2\times 10^5, 2N))\) là số câu hỏi.
• \(Q\) dòng tiếp theo, dòng thứ \(i ~ (1 \leq i \leq Q)\) chứa một số nguyên dương \(v_i ~ (1 \leq v_i \leq 10^9)\) thể hiện câu hỏi thứ \(i\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i ~ (1 \leq i \leq Q)\) chứa một số nguyên duy nhất là số gàu nước ít nhất mà chú tiểu cần liên tục đổ nước vào để cả \(N\) gàu nước đều đầy sau không quá \(v_i\) giây, hoặc đưa ra \(-1\) nếu không tồn tại cách đổ nước thỏa mãn yêu cầu.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \leq 20, v_i \leq 1000\).
• Subtask \(2\) (\(15\%\) số điểm): \(N \leq 5000, v_i \leq 6000\).
• Subtask \(3\) (\(75\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
4 1 5 4 1
3
5
3
4

3
-1
4