Có \(𝑛\) đống sỏi được xếp thành một hàng ngang và được đánh số từ \(1\) đến \(𝑛\) theo chiều từ trái sang phải. Đống sỏi thứ \(𝑖\) có \(𝑎_𝑖\) viên sỏi. Có hai thao tác thực hiện trên các đống sỏi.
1. Gộp hai đống sỏi kề nhau thành 1 đống sỏi.
2. Tách 1 đống sỏi thành 2 đống kề nhau (tức là thay thế 1 đống sỏi, thành 2 đống sỏi với tổng số viên sỏi của đống ban đầu bằng số sỏi của hai đống được tách ra.
Có \(𝑞\) yêu cầu, với mỗi yêu cầu cho một số nguyên dương \(𝑥\). Tính xem, cần thực hiện ít nhất bao nhiêu thao tác dạng trên để từ dãy sỏi ban đầu, ta nhận được một dãy sỏi mà mỗi đống sỏi đều có đúng \(𝑥\) viên sỏi.
Input:
• Dòng 1 ghi số nguyên dương \(𝑛\) là số đống sỏi.
• Dòng 2 ghi \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, \dots , 𝑎_𝑛 (1 \leq 𝑎_𝑖 \leq 10^{18} )\).
• Dòng 3 ghi số nguyên dương \(𝑞\) \((1 \leq 𝑞 \leq 100 000)\).
• \(𝑞\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(𝑥\) \((1 \leq 𝑥 \leq 10^{18})\).
Output:
\(𝑞\) dòng, mỗi dòng ghi một số nguyên là kết quả của truy vấn tương ứng. Nếu không có cách thực hiện thao tác để nhận được dãy sỏi mà mỗi đống có \(𝑥\) viên sỏi thì ghi \(−1\).
o Truy vấn 1: 𝑥 = 1.
Ta có các thao tác sau:
[1, 2, 3, 1, 1, 4]
→ [1, 1, 1, 3, 1, 1, 4]
→ [1, 1, 1, 1, 2, 1, 1, 4]
→ [1, 1, 1, 1, 1,1, 1, 1, 4]
→ [1, 1, 1, 1, 1,1, 1, 1, 1, 3]
→ [1, 1, 1, 1, 1,1, 1, 1, 1, 1, 2]
→ [1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1]
o Truy vấn 5: 𝑥 = 5.
Tổng các đống sỏi 1 + 2 + 3 + 1 + 1 + 4 = 12 không chia hết cho 5 nên không thể chia các đống có số sỏi bằng 5.
o Truy vấn 3, 𝑥 = 3.
Ta có các thao tác sau:
[1, 2, 3, 1, 1, 4].
→ [3, 3, 1, 1, 4]
→ [3, 3, 2, 4]
→ [3, 3, 6]
→ [3, 3, 3, 3]