Trò chơi giáo dục

Cho dãy gồm $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$.

Một nước đi được thực hiện như sau: chọn một chỉ số $i$ ($1\le i\le n$) sao cho $a_i>0$ và một số nguyên $t\ge 0$ sao cho $i+2^t\le n$, rồi giảm $a_i$ đi $1$ và tăng $a_{i+2^t}$ lên $1$. Nói cách khác, ta chuyển một đơn vị từ vị trí $i$ sang vị trí $i+2^t$, với khoảng cách nhảy luôn là một luỹ thừa của $2$.

Ví dụ, với $n=4$ và $a=(1,0,1,2)$, ta có thể chọn $i=3,t=0$ để được $a=(1,0,0,3)$, hoặc chọn $i=1,t=1$ để được $a=(0,0,2,2)$.

Với mỗi $k$ từ $1$ đến $n-1$, hãy tính số nước đi ít nhất cần thực hiện để $k$ phần tử đầu tiên $a_1,a_2,\dots ,a_k$ đều bằng $0$.

Các giá trị $k$ được xét hoàn toàn độc lập với nhau: mỗi câu trả lời đều được tính từ dãy ban đầu, chứ không phải từ dãy sau khi đã xử lý $k$ nhỏ hơn.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra đúng $n-1$ dòng. Dòng thứ $k$ chứa số nước đi ít nhất cần thiết để $a_1,a_2,\dots ,a_k$ đều bằng $0$.

Ràng buộc

• $2\le n\le 2000$
• $0\le a_i\le {10}^4$

Ví dụ