Ngủ Trong Lớp (Khó)

Bessie hay ngủ gật trong lớp, và bạn thân Elsie đã ghi lại nhật ký theo dõi gồm $N$ tiết học, trong đó tiết thứ $i$ Bessie ngủ gật $a_i$ lần.

Elsie muốn chỉnh sửa nhật ký theo hai loại thao tác:

• Gộp: Chọn hai tiết liền kề, gộp thành một tiết duy nhất có số lần ngủ gật bằng tổng hai tiết cũ (số tiết giảm đi 1).
• Tách: Chọn một tiết có giá trị $v$, tách thành hai tiết liền kề với giá trị lần lượt là $x$ và $v-x$ (với $1\le x\le v-1$, số tiết tăng lên 1).

Cho $Q$ truy vấn. Với mỗi truy vấn có giá trị $d$, hãy tìm số thao tác tối thiểu để làm cho tất cả các tiết học đều có số lần ngủ gật đúng bằng $d$, hoặc in ra $-1$ nếu không thể.

Dữ liệu vào

• Dòng 1: Số nguyên $N$ ($2\le N\le {10}^5$)
• Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$ ($1\le a_i\le {10}^{18}$, tổng $\sum a_i\le {10}^{18}$)
• Dòng 3: Số nguyên $Q$ ($1\le Q\le {10}^5$)
• $Q$ dòng tiếp theo: Mỗi dòng chứa số nguyên $d_i$ ($1\le d_i\le {10}^{18}$)

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên trên một dòng — số thao tác tối thiểu, hoặc $-1$ nếu không thể.

Ràng buộc

• $2\le N\le {10}^5$, $1\le Q\le {10}^5$
• $1\le a_i\le {10}^{18}$, tổng $S={\sum }_{i=1}^N{a}_i\le {10}^{18}$
• $1\le d_i\le {10}^{18}$
• Test 2-4: $N,Q\le 5000$
• Test 5-7: tất cả $a_i\le {10}^9$
• Test 8-26: không có ràng buộc thêm

Ví dụ

Ghi chú

Không thể đạt $d=5$ trong ví dụ 1 vì tổng $S=12$ không chia hết cho 5 — dù có bao nhiêu thao tác cũng không thể chia đều.

Một thao tác tách hoặc gộp đều được tính là 1 thao tác.