C. Хашаа будав.

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

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

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

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

Бизон аварга зүгээр ч анхааралтай хүн биш бөгөөд бас маш ажилсаг нэгэн юм.

Бизон хуучин хашаагаа өөрийн дуртай өнгө болох улбар шар өнгөөр будхаар болов. Хашаа нь дарааллуулан тавьсан $n$ ширхэг босоо банзаар хийгдсэн. Зэрэгцээ хоёр банзны ямар ч зай байхгүй. Банзнууд нь зүүнээс баруун тийш нэг нэгээрээ дугаарлагдсан ба $i$-р банзны өргөн нь $1$ метр, өндөр нь $a_{i}$ метр байна.

Бизон дэлгүүрээс $1$ метрийн өргөнтэй багс худалдаж авав. Тэр багсаа босоо болон хэвтээ барьж багсдаж чадах ба хашааны бүтэн гадаргууг дуустал тасралтгүй багсдаж чадна (жишээг харвал илүү сайн ойлгоно). Бизон бүх банзыг будаж дуусгахын тулд хамгийн багадаа хэдэн удаа багсдах вэ? Банзны ижил хэсгийг олон удаа будаж болохыг анхаараарай.

Оролт

Эхний мөрөнд $n$ $(1 ≤ n ≤ 5000)$ бүхэл тоог оруулна. Энэ нь хашааны банзны тоо. Хоёрдугаар мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо болох $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{9})$-г оруулна.

Гаралт

Ганц бүхэл тоо хэвлэнэ. Энэ тоо нь бүх хашааг будахад хамгийн багадаа хэдэн удаа багсдахыг илэрхийлнэ.

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

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

Оролт
5
2 2 1 2 1
Гаралт
3
Оролт
2
2 2
Гаралт
2
Оролт
1
5
Гаралт
1

Тэмдэглэл

Эхний жишээний хашааг будахын тулд гурван удаа багсдах хэрэгтэй: Эхний удаад багсаа босоо барьж бүх банзыг хөндлөнгөөр нь багсдана. Хоёрдугаар багсдалт нь мөн босоо барьж эхний болон хоёрдугаар банзыг хөндлөнгөөр нь багсдах ба гуравдугаар багсдалт нь дөрөвдүгээр банзыг багсдаад(босоо хэвтээ аль ч чиглэлээр болно) дуусна. Жишээ хоёрт банзнуудыг хэвтээ эсвэл босоо чиглэлд хоёр удаа багсдаад будаж дуусна. Гуравдугаар жишээнд ганцхан банз байгаа тул босоогоор нь нэг удаа багсдаад будаж дуусгана.

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