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

Кайса зам зууртаа гар утасны тоглоом тоглон явж байна. Тэр тоглоомонд $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})$ агуулна.

Гаралт

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

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