Trang trại VNMILK 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~ ~(1 \le i \le 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). Hãy 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.

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.

Input

• Dòng đầu chứa số nguyên dương ~N~ ~(N < 10^5)~.

• Các dòng tiếp theo chứa ~N~ số nguyên dương ~a_i~ ~(1 \le i \le N)~ thể hiện số sữa tương ứng của ~N~ con bò.

Output

• Dòng thứ nhất thể hiện số lượng sữa tối đa có thể thu được.

• Dòng thứ hai cho biết số lượng sữa vắt được của từng con bò, mỗi số cách nhau một khoảng trắng.

Sample Input 1

6
1
8
10
9
2
5

Sample Output 1

26
10 8 6 2 0 0