Vào sáng sớm, bác nông dân John thức giấc vì tiếng gỗ vỡ vụn. Lại là đàn bò, và chúng lại đang phá chuồng trốn ra ngoài!

Bác nông dân John đã quá chán ngán những vụ phá chuồng vào buổi sáng của đàn bò và quyết định rằng như thế là đủ: đã đến lúc phải mạnh tay. Ông đóng lên tường chuồng một bộ đếm theo dõi số ngày kể từ vụ phá chuồng gần nhất. Vì vậy, nếu một vụ phá chuồng xảy ra vào buổi sáng thì bộ đếm trong ngày đó sẽ là \(0\); nếu vụ phá chuồng gần nhất xảy ra \(3\) ngày trước thì bộ đếm sẽ hiển thị \(3\). Bác nông dân John ghi lại giá trị của bộ đếm mỗi ngày một cách cẩn thận.

Cuối năm đã đến và bác nông dân John sẵn sàng tính sổ. Lũ bò sẽ phải trả giá, ông nói! Nhưng có điều gì đó trong nhật ký của ông trông không ổn...

Bác nông dân John muốn tìm xem đã có bao nhiêu vụ phá chuồng xảy ra kể từ khi ông bắt đầu ghi nhật ký. Tuy nhiên, ông nghi ngờ đàn bò đã sửa nhật ký, và điều duy nhất ông biết chắc là ông bắt đầu ghi nhật ký đúng vào ngày xảy ra một vụ phá chuồng. Với mỗi số vụ phá chuồng có thể đã xảy ra kể từ khi ông bắt đầu ghi nhật ký, hãy giúp ông xác định số mục nhật ký ít nhất buộc phải bị sửa.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \leq N \leq 100\)), biểu thị số ngày kể từ khi bác nông dân John bắt đầu ghi lại bộ đếm các vụ phá chuồng của đàn bò.

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách. Số nguyên thứ \(i\) là một số nguyên không âm \(a_i\) (không quá \(100\)), cho biết bộ đếm ở ngày \(i\) có giá trị \(a_i\), trừ khi đàn bò đã sửa mục nhật ký của ngày đó.

Dữ liệu ra

Kết quả gồm \(N\) số nguyên, mỗi số trên một dòng. Số nguyên thứ \(i\) là số mục nhật ký không phù hợp nhỏ nhất trong tất cả các chuỗi phá chuồng có đúng \(i\) vụ phá chuồng.

Ví dụ

6
1 1 2 0 0 1

4
2
1
2
3
4

Nguồn

USACO 2018 February Contest, Gold — Taming the Herd

Tác giả bài toán: Brian Dean và Dhruv Rohatgi.