C. Үнэг ба хайрцагны хуримтлал

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сиел үнэгний өрөөнд $n$ хайрцаг байна. Тэд ижил хэмжээ болон жинтэй боловч өөр өөр чадалтай. $i$-р хайрцагны дээр хамгийн ихдээ $x_{i}$ хайрцгуудыг тавьж болно (бид $x_{i}$-г хайрцагны чадал гэе).

Бүх хайрцаг ижил хэмжээтэй тул Сиел зарим хайрцагны орой дээр шууд нэгээс илүү хайрцаг тавьж чадахгүй байна. Жишээлбэл, Сиелд гурван хайрцаг байна гэж бодъё: эхний хайрцагны чадал 2, хоёр дахь хайрцагны чадал 1, гурав дахь хайрцагны чадал 1. Тэр хоёр ба гуравдугаар хайрцагны дээр нэг зэрэг шууд нэгдүгээр хайрцгыг тавьж чадахгүй. Гэхдээ нэгдүгээр хайрцагны дээр хоёрдугаар хайрцгыг, дараа нь хоёрдугаар хайрцагны дээр гуравдугаар хайрцгыг шууд тавьж чадна. Бид үүнийг хайрцагнуудын овоолгон барилга гэж нэрлэж болно.

Сиел үнэг бүх хайрцгаар овоолго барихыг хүссэн. Овоолго бүр нь дээрээс доошоо зарим хайрцгуудыг агуулах ба $i$-р хайрцагны дээр $x_{i}$-с илүү хайрцаг байж болохгүй. Түүний барих овоолгоны хамгийн бага тоо хэд вэ?

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 100$) бүхэл тоог агуулна. Дараагийн мөрөнд $n$ ширхэг бүхэл тоонууд $x_{1}, x_{2}, ..., x_{n}$ ($0 ≤ x_{i} ≤ 100$) байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ бол овоолгоны боломжит хамгийн бага тоо.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3
0 0 10
Гаралт
2
Оролт
5
0 1 2 3 4
Гаралт
1
Оролт
4
0 0 0 0
Гаралт
4
Оролт
9
0 1 0 2 0 1 1 2 10
Гаралт
3

Тэмдэглэл

Жишээ 1, нэг арга нь 2 овоолго барих явдал юм: эхний овоолгод 1 болон 3-р (дээрээсээ доош) хайрцаг агуулагдана, хоёр дахь овоолгод нь зөвхөн 2-р хайрцаг агуулагдана.

Жишээ 2, Бид 1, 2, 3, 4, 5 (дээрээс доошоо) хайрцгуудаар нэг л овоолго барьж чадна.

Сэтгэгдлүүдийг ачааллаж байна...