B. Кайса ба баганууд

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

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

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

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

Кайса элсэн чихрийн бодлогыг бодоод одоо гэртээ харьж байна.

Кайса зам зууртаа гар утасны тоглоом тоглон явж байна. Тэр тоглоомонд $0$-ээс $n$ дугаартай $(n + 1)$ багана байв. $0$ дугаартай багана тэг ѳндѳртэй, $i$ $(i > 0)$ дугаартай багана $h_{i}$ ѳндѳртэй. Тоглоомын зорилго нь $n$-р баганад зѳвхѳн байгаа баганаасаа дараагийн багана бүрт харайсаар очих юм ($k$ дугаартай баганаас зѳвхѳн $k + 1$ дугаартай багана руу л үсэрч болно). Энэ шилжилт хийх бүрт түүний энерги $h_{k} - h_{k + 1}$ (хэрвээ энэ утга сѳрѳг байвал энерги нь багасна) хэмжээгээр нэмэгднэ. Тоглогч аль ч агшинд сѳрѳг биш энергитэй байх ёстой.

Анх Кайса $0$ багана дээр байхад $0$ энергитэй байна. Энэ тоглоом нэгэн онцгой боломжийг ѳгдѳг: ганц доллар тѳлѳѳд дуртай баганыхаа ѳндрийг нэгээр ѳсгѳж болно. Кайса энэхүү боломжийг хэдэн ч удаа ашиглах боломжтой ч тэр үүнд их мѳнгѳ зориулахыг хүсэхгүй байлаа. Түүнд тоглоомыг давахын тулд хамгийн багадаа хэдэн доллар шаардлагатай вэ?

Оролт

Эхний мѳр $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоог агуулна. Дараагийн мѳр багануудын ѳндѳр болох $n$ ширхэг бүхэл тоо $h_{1}$, $h_{2}$, ..., $h_{n}$ $(1  ≤  h_{i}  ≤  10^{5})$ агуулна.

Гаралт

Кайсагийн тѳлѳх ёстой хамгийн бага долларын хэмжээ болох бүхэл тоог хэвлэ.

Орчуулсан: Sugardorj

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

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

Тэмдэглэл

Эхний жишээний хувьд $4$ доллар тѳлѳѳд $0$ дугаартай баганы ѳндрийг $4$ нэгжээр ѳсгѳхѳд сүүлийн багана хүртэл явж чадна.

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