Bài tập

Vương quốc Berland có \(n\) công dân, công dân thứ \(i\) đang nhận phúc lợi \(a_i\) đồng burle. Nhà vua muốn mọi người có phúc lợi bằng nhau, và chỉ được tăng phúc lợi của ai đó (lấy từ ngân khố), không được lấy bớt của ai.

Hãy tính tổng số burle ít nhất mà ngân khố phải chi để tất cả công dân có phúc lợi bằng nhau.

Input

• Dòng đầu: số nguyên \(n\).
• Dòng thứ hai: \(n\) số nguyên \(a_1, \dots, a_n\).

Output

Một số nguyên: tổng chi phí nhỏ nhất.

Constraints

• \(1 \le n < 100\)
• \(|a_i| < 10^6\)

Sample Input

5
3 9 1 9 4

Sample Output

19

Explanation

Nâng mọi người lên mức \(9\): \(6 + 0 + 8 + 0 + 5 = 19\).

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.

Trên một dải gồm \(N\) ô xếp thành hàng, ô thứ \(i\) (\(1 \le i \le N\)) chứa một số nguyên \(a_i\) (có thể âm). Quân cờ ban đầu nằm ở ô số \(0\) (ô xuất phát, không chứa giá trị) và tổng điểm bằng \(0\).

Mỗi lượt đi, quân cờ tiến sang phải ít nhất \(1\) và nhiều nhất \(K\) ô. Mỗi khi hạ cánh xuống ô \(i\), giá trị \(a_i\) được cộng vào tổng điểm (các ô bị nhảy qua không được tính). Người chơi có thể dừng lại tại bất kỳ thời điểm nào, kể cả khi chưa đi lượt nào (khi đó điểm là \(0\)), nhưng không được đi ra ngoài ô \(N\).

Hãy tính tổng điểm lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• In ra một số nguyên: tổng điểm lớn nhất.

Constraints

• \(1 \le N \le 10^5\)
• \(1 \le K \le 100\)
• \(-10^9 \le a_i \le 10^9\)

Sample Input

7 3
-4 2 -7 -5 -6 8 -1

Sample Output

5

Explanation

Đi theo các ô \(2 \to 4 \to 6\) (mỗi lượt bước không quá \(3\) ô) thu được \(2 + (-5) + 8 = 5\). Sau đó dừng lại. Không có cách nào tốt hơn.

Một phi thuyền xuất phát tại toạ độ \(K\) trên một trục số. Mỗi lần "nhảy", phi thuyền có thể dịch chuyển đến một trong bốn vị trí: \(x + d_1\), \(x - d_1\), \(x + d_2\) hoặc \(x - d_2\) (với \(x\) là vị trí hiện tại). Phi thuyền có thể nhảy bao nhiêu lần tuỳ ý và đi qua các toạ độ nguyên bất kỳ, kể cả toạ độ âm.

Trên trục có \(N\) hành tinh, hành tinh thứ \(i\) ở toạ độ \(X_i\). Một hành tinh được xem là thăm được nếu phi thuyền có thể đáp xuống đúng toạ độ đó (nếu \(X_i = K\) thì không cần nhảy).

Hãy đếm số hành tinh thăm được.

Input

• Dòng đầu chứa bốn số nguyên \(N, K, d_1, d_2\).
• Dòng thứ hai chứa \(N\) số nguyên \(X_1, \dots, X_N\).

Output

In ra một số nguyên: số hành tinh thăm được.

Constraints

• \(1 \le N \le 10^5\).
• \(|K| \le 10^9\).
• \(1 \le d_1, d_2 \le 10^9\).
• \(-10^9 \le X_i \le 10^9\).

Sample Input

5 3 6 9
0 6 7 -6 12

Sample Output

4

Explanation

Từ toạ độ \(3\) với các bước \(6\) và \(9\), phi thuyền chỉ đến được những toạ độ có hiệu với \(3\) chia hết cho \(3\). Các toạ độ \(0, 6, -6, 12\) thoả mãn, còn \(7\) thì không.