Cân bằng công suất

Một lưới điện có \(N\) trạm phát, công suất hiện tại của trạm thứ \(i\) là số nguyên \(A_i\) (có thể âm). Mỗi thao tác chọn hai trạm khác nhau \(i \neq j\), rồi tăng \(A_i\) lên \(1\) và giảm \(A_j\) đi \(1\) (tổng công suất không đổi).

Có \(T\) ngưỡng \(D_1, D_2, \dots, D_T\). Các ngưỡng được xét độc lập: với mỗi \(D\), ta xuất phát từ dãy \(A\) ban đầu và cần thực hiện ít thao tác nhất sao cho hiệu giữa công suất lớn nhất và nhỏ nhất trong dãy không vượt quá \(D\), tức \(|A_x - A_y| \le D\) với mọi cặp \(x, y\). Hãy tính số thao tác tối thiểu đó cho từng ngưỡng.

Input

• Dòng đầu: hai số nguyên \(N\) và \(T\).
• Dòng thứ hai: \(N\) số nguyên \(A_1, \dots, A_N\).
• Dòng thứ ba: \(T\) số nguyên \(D_1, \dots, D_T\).

Output

In ra \(T\) dòng; dòng thứ \(k\) là số thao tác tối thiểu ứng với ngưỡng \(D_k\).

Constraints

• \(1 \le N, T \le 10^6\)
• \(|A_i| \le 10^6\)
• \(1 \le D_k \le 10^6\)

Chấm điểm theo subtask:

• Subtask 1 (20%): \(N, T \le 10\), \(|A_i| \le 1000\).
• Subtask 2 (40%): \(N, T \le 1000\).
• Subtask 3 (40%): không có ràng buộc thêm.

Sample Input

4 2
1 7 3 5
3 1

Sample Output

2
4

Explanation

Với \(D=3\): thao tác \((i=1,j=2)\) rồi \((i=3,j=2)\) cho dãy \([2,5,4,5]\) có chênh lệch \(3\); một thao tác thì chưa đủ nên đáp án là \(2\). Với \(D=1\): bắt buộc đưa về \([4,4,4,4]\), cần \(4\) thao tác.