B. Зам дагуух мод (хялбаршуулсан хувилбар)

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

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

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

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

Лисс хэрэм самранд дуртай. Гудамжны дагуу баруунаас зүүн тийш $1$-ээс эхлэн $n$ хүртэл дугаарлагдсан $n$ ширхэг моднууд байдаг бөгөөд мод бүрийн орой дээр амттай самар байдаг. $i$-р мод $h_{i}$ өндөртэй байна. Лисс бүх самрыг идэхийг хүсчээ.

Одоо Лисс $1$-ээр модны доор байна. Тэр секундэд дараах үйлдлүүдийн аль нэгийг гүйцэтгэж чадна:

  • Модон дээр нэг нэгжээр доошоо эсвэл дээшээ явна.
  • Одоогийн модны дээр байгаа самрыг иднэ.
  • Дараагийн мод руу үсрэнэ. Энэ үйлдлээр Лиссийн байгаа өндөр өөрчлөгдөхгүй. Томъёолбол Лисс $i$ ($1 ≤ i ≤ n - 1$) модны $h$ өндөрт байхдаа $i + 1$-р модны $h$ өндөрлүү үсрэнэ. Хэрвээ $h > h_{i + 1}$ бол энэ үйлдлийг хийж чадахгүй.

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

Оролт

Эхний мөрөнд моднуудын тоо болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоо байна.

Дараагийн $n$ мөрүүдэд моднуудын өндөр байна: $i$-р мөрөнд $h_{i}$ ($1 ≤ h_{i} ≤ 10^{4}$) бүхэл тоо байна. Энэ нь $i$-р модны өндөр юм.

Гаралт

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

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

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

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