Bò Bessie rất hào hứng vì gần đây đã được quay lại học trực tiếp! Đáng tiếc, giáo viên của cô, Farmer John, giảng bài rất nhàm chán nên cô thường xuyên ngủ gật trong lớp.

Farmer John nhận thấy Bessie không chú ý trong giờ học. Ông nhờ một học sinh khác trong lớp là Elsie ghi lại số lần Bessie ngủ gật trong mỗi buổi học. Có \(N\) buổi học (\(2\le N\le 10^5\)), và Elsie ghi nhận rằng Bessie ngủ gật \(a_i\) lần (\(1\le a_i\le 10^{18}\)) trong buổi học thứ \(i\). Tổng số lần Bessie ngủ gật trong tất cả các buổi học không vượt quá \(10^{18}\).

Vì rất thích cạnh tranh với Bessie, Elsie muốn khiến Farmer John nghĩ rằng Bessie luôn ngủ gật cùng một số lần trong mọi buổi học — qua đó làm cho vấn đề có vẻ hoàn toàn là lỗi của Bessie, không phụ thuộc vào những bài giảng đôi khi nhàm chán của Farmer John.

Elsie chỉ được phép sửa nhật ký bằng cách gộp hai buổi học kề nhau hoặc tách một buổi học thành hai. Ví dụ, nếu \(a=[1,2,3,4,5]\) và Elsie gộp buổi học thứ hai với buổi học thứ ba, nhật ký sẽ trở thành \([1,5,4,5]\). Nếu sau đó Elsie chọn tách buổi học thứ ba thành hai, nhật ký có thể trở thành một trong các dãy \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\) hoặc \([1,5,4,0,5]\).

Cho \(Q\) (\(1\le Q\le 10^5\)) ứng viên \(q_1,\ldots,q_Q\) cho con số Bessie ít yêu thích nhất (\(1\le q_i\le 10^{18}\)), với mỗi ứng viên hãy giúp Elsie tính số lần sửa nhật ký ít nhất cần thực hiện để tất cả các số trong nhật ký trở nên bằng nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), dòng thứ hai chứa \(a_1,a_2,\ldots,a_N\). Dòng thứ ba chứa \(Q\), sau đó là \(Q\) dòng, mỗi dòng chứa một số nguyên \(q_i\), một ứng viên cho con số Bessie ít yêu thích nhất.

Dữ liệu ra

Với mỗi \(q_i\), hãy in số lần sửa ít nhất cần thiết để Elsie biến mọi phần tử trong nhật ký thành \(q_i\), hoặc \(-1\) nếu điều đó là không thể.

Phân nhóm

• Trong các test 2–4, \(N,Q\le 5000\).
• Trong các test 5–7, mọi \(a_i\) không vượt quá \(10^9\).
• Các test 8–26 không có ràng buộc bổ sung.

Ví dụ

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

6
6
4
5
-1
4
5

   1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3

Nguồn

USACO 2022 February Contest, Platinum — Sleeping in Class: https://usaco.org/index.php?page=viewproblem2&cpid=1213

Tác giả: Jesse Choe và Benjamin Qi.