Câu 3. SỮA BÒ (4,0 điểm; Đề TS vào 10 – Khoa học Huế 2026 – 2027 vòng 2)

Trang trại VINMILK sản xuất sữa tươi để phục vụ nhu cầu của khách hàng. Để đạt được sản lượng tốt nhất, chủ trang trại đã nuôi dưỡng và chăm sóc N con bò sữa để cho ra những hộp sữa tươi chất lượng.
Biết rằng với N con bò sữa, con thứ i (i = 1..N) cho sản lượng sữa a_i lít trong mỗi lần vắt sữa. Tuy nhiên, mỗi khi vắt sữa một con bò thì những con còn lại sẽ e sợ và số sữa giảm đi 1 lít (cho đến khi số sữa về 0 thì không thể vắt được nữa).
Yêu cầu: Tính số lượng sữa tối đa có thể thu được và cho biết số lượng sữa vắt được của từng con bò để thu được nhiều lít sữa nhất.
Dữ liệu vào:

• Gồm một số nguyên dương N (N < 10⁵).
• Tiếp theo là N số nguyên dương a_i (i = 1..N) thể hiện số sữa tương ứng của N con bò.

Dữ liệu ra:

• Dòng thứ nhất ghi số lượng sữa tối đa có thể thu được.
• Dòng thứ hai ghi số lượng sữa vắt được của từng con bò theo phương án tối ưu, các số cách nhau bởi một dấu cách.

Ví dụ: