Đồi

Cho dãy $n$ ngọn đồi với chiều cao lần lượt là $a_1,a_2,\dots ,a_n$. Người ta muốn xây nhà trên một số ngọn đồi, nhưng để đảm bảo mỹ quan, một ngôi nhà chỉ có thể đặt trên ngọn đồi cao hơn nghiêm ngặt cả hai ngọn đồi kề (nếu có).

Ví dụ với dãy chiều cao $5,4,6,2$ thì chỉ có thể xây nhà trên ngọn đồi chiều cao $5$ và ngọn đồi chiều cao $6$.

Có một chiếc máy xúc có thể giảm chiều cao của một ngọn đồi tuỳ ý đi $1$ đơn vị trong $1$ giờ làm việc. Máy xúc chỉ làm việc trên một ngọn đồi tại một thời điểm. Chiều cao có thể giảm xuống $0$ hoặc thậm chí âm. Không thể tăng chiều cao bất kỳ ngọn đồi nào.

Với mỗi $k$ từ $1$ đến $\lceil n/2\rceil$, hãy tính số giờ tối thiểu cần thiết để san phẳng các ngọn đồi sao cho có ít nhất $k$ ngọn đồi đủ điều kiện xây nhà.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số ngọn đồi.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — chiều cao các ngọn đồi.

Dữ liệu ra

In ra đúng $\lceil n/2\rceil$ số nguyên trên một dòng, cách nhau bởi dấu cách. Số thứ $i$ là số giờ tối thiểu để có thể xây được ít nhất $i$ ngôi nhà.

Ràng buộc

• $1\le n\le 5000$
• $1\le a_i\le 100000$

Ví dụ