Mô tả và yêu cầu

IDGAME
Trò chơi IDGAME là trò chơi trên một dãy số nguyên 𝑎1, 𝑎2, … ,𝑎𝑛. Mỗi lượt người chơi được
thực hiện thao tác chọn hai phần tử 𝑖, 𝑗 (1 ≤ 𝑖 ≠ 𝑗 ≤ 𝑛) rồi tăng 𝑎𝑖 lên 1 và giảm 𝑎𝑗 đi 1. Với một
số nguyên 𝐷 cho trước, người chơi cần tìm cách biến đổi dãy số ban đầu thành một dãy số mới mà
chênh lệch giữa hai phần tử bất kì trong dãy mới không vượt quá 𝐷 với số thao tác là ít nhất.
Yêu cầu: Cho dãy số nguyên 𝑎1,𝑎2, … ,𝑎𝑛 và 𝑇 số nguyên dương 𝐷1, 𝐷2, … , 𝐷𝑇. Với mỗi 𝑇𝑠 (1 ≤
𝑠 ≤ 𝑇) hãy tính số thao tác ít nhất để biến đổi dãy số ban đầu thành một dãy số mới mà chênh lệch
giữa hai phần tử bất kì trong dãy mới không vượt quá 𝐷𝑠.

Dữ liệu vào

- Dòng đầu chứa hai số nguyên dương 𝑛, 𝑇;
- Dòng thứ hai gồm 𝑛 số nguyên 𝑎1, 𝑎2, … ,𝑎𝑛.
- Dòng thứ ba gồm 𝑇 số nguyên dương 𝐷1, 𝐷2, … ,𝐷𝑇.

Dữ liệu ra

- Gồm 𝑇 dòng, dòng thứ 𝑠 (1 ≤ 𝑠 ≤ 𝑇) chứa một số nguyên là thao tác ít nhất cần thực hiện
tương ứng với trường hợp 𝑇𝑠.
IDGAME.INP IDGAME.OUT
4 2 1
5 3 2 4 1
1 2

Subtask 1: 𝑛 ≤ 10; 𝑇 = 1; |𝑎𝑖| ≤ 10;
Subtask 2: 𝑛 ≤ 106; 𝑇 ≤ 106; |𝑎𝑖| ≤ 106;