BT có thói quen ghi nhật ký để nhớ lại những ngày xảy ra sự kiện trọng đại trong đời mình. Để đơn giản, khi một ngày có sự kiện xảy ra anh ta ghi số 0, ngày tiếp theo nếu không có sự kiện nào xảy ra anh ta ghi số 1, ngày tiếp theo nếu không có sự kiện trọng đại nào ghi số 2,.... Như vậy nhật ký của BT có thể mô tả bằng dãy số dạng như ví dụ dưới đây:

0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1, .....

Sau n ngày, BT đọc lại nhật ký của mình và phát hiện rằng dãy số trong nhật ký không đúng. Điều này có thể là do lỗi máy tính hoặc do ai đó đã cố tình sửa nhật ký của anh ta. Buồn hơn nữa là anh ta cũng không nhớ được đã có bao nhiêu sự kiện trọng đại xảy ra. BT quyết định thử xem nếu giả thiết có k sự kiện trọng đại xảy ra thì trong trường hợp tốt nhất bản nhật ký mà anh ta giữ sẽ sai khác ít nhất so với nhật ký đúng bao nhiêu giá trị?.

Yêu cầu: hãy giúp BT thực hiện điều trên với các giá trị k=1,2,…,n.

Input:

• Dòng đầu tiên chứa số nguyên dương n≤100 là số ngày BT ghi nhật ký

• Dòng thứ hai chứa n số nguyên lần lượt là dãy số ghi trong nhật ký của BT bắt đầu từ ngày 1 đến ngày n.

Output:

In ra n số nguyên, mỗi số trên một dòng, dòng thứ k là số giá trị khác nhau ít nhất có thể có khi so sánh dãy số của BT với một nhật ký đúng có k sự kiện trọng đại xảy ra.

Sample Input

6
1 1 2 0 0 1

Sample Output

4
2
1
2
3
4

Giải thích

Giải thích: Nếu có 1 sự kiện xảy ra nhật ký đúng là 0, 1, 2, 3, 4, 5 khác với nhật ký BT 4 vị trí. Nếu có 2 sự kiện xảy ra thì nhật ký đúng tốt nhất là 0, 1, 2, 3, 0, 1 khác với nhật ký của BT 2 vị trí. Nếu có 3 sự kiện xảy ra thì nhật ký đúng tốt nhất là 0 1 2 0 0 1 khác với nhật ký của BT 1 vị trí. Làm tương tự với các trường hợp có 4 hoặc 5 sự kiện xảy ra