Xây nhà trên đồi

Thành phố có một dãy $n$ ngọn đồi xếp thành hàng ngang, ngọn đồi thứ $i$ có độ cao $a_i$.

Người ta muốn xây nhà trên các ngọn đồi. Vì lý do thẩm mỹ, một ngôi nhà chỉ được xây trên ngọn đồi cao hơn hẳn (lớn hơn thực sự) mọi ngọn đồi kề nó. Đồi thứ $1$ chỉ có một đồi kề là đồi thứ $2$, đồi thứ $n$ chỉ có một đồi kề là đồi thứ $n-1$; các đồi còn lại có hai đồi kề. Ví dụ với dãy độ cao $5,4,6,2$ thì chỉ có thể xây nhà trên hai ngọn đồi có độ cao $5$ và $6$.

Thành phố có một chiếc máy xúc. Trong một giờ, máy xúc làm giảm độ cao của đúng một ngọn đồi đi $1$ đơn vị. Máy chỉ làm việc trên một ngọn đồi tại một thời điểm. Độ cao được phép giảm xuống $0$ hoặc xuống giá trị âm. Không có cách nào làm tăng độ cao của một ngọn đồi.

Chính quyền muốn xây $k$ ngôi nhà, tức là sau khi san đồi phải có ít nhất $k$ ngọn đồi thoả điều kiện ở trên. Vì giá trị $k$ chưa được chốt, hãy tính đáp án cho mọi $k$ từ $1$ đến $\lceil n/2\rceil$: với mỗi $k$, cho biết số giờ ít nhất cần dùng máy xúc.

Dữ liệu vào

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

Dữ liệu ra

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

Ràng buộc

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

Ví dụ