D. Байшин

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

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

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

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

D хот нэг шулуунд баригдсан $n$ байшинтай. $i$-дэх (зүүнээс баруун тийш) байшингийн өндөр нь $h_{i}$. Хотын дарга шинэчлэлт хийж хотоо үзэсгэлэнтэй харагдуулах гэж байгаа. Үзэсгэлэнтэй харагдуулахын тулд байшингийн өндрүүд нь зүүнээс баруун луу үл буурахаар байх ёстой.

Шинэчлэлт хийх гэдэг нь дараах хэдэн (магадгүй тэг) үйлдлээс тогтоно. Энэ үйлдэл нь: Нэг байшинг хөрш байшин дээр нь залгахыг хэлнэ. Өөрөөр хэлбэл $i$-дэх байшинг $(i - 1)$-дэх байшин (хэрвээ байшин байвал) дээр эсвэл $(i + 1)$-дэх байшин (хэрвээ байшин байвал) дээр залгаж тавьж болно. Ингэснээр тэр байшингийн өндөр 2 байшингийн өндрийг нэмсэнтэй тэнцүү болох болно бас нийт байшингийн тоо нэгээр багасах болно. Нийлүүлсэн 2 байшинг салгаж болохгүй харин дээр нь дахиад байшин залгаж болно.

Хотын даргад хамгийн бага үйлдлээр хотыг үзгэслэнтэй харагдуулахад нь туслана уу.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 5000$) байшингийн тоо. Дараагийн мөрөнд $i$ -дэх байшингийн өндөр болох $h_{i}$ ($1 ≤ h_{i} ≤ 10^{5}$) .

Гаралт

Хамгийн бага үйлдлийн тоо болох ганц тоо.

Орчуулсан: anhaabc

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

Оролт
5
8 2 7 3 1
Гаралт
3
Оролт
3
5 2 1
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...