Muallif: __thecrash__

E. Minimal enirgiya

Vaqt limiti: 1000 ms Xotira limiti: 128 mb

Bir qatorda ketma-ket \(n\) ta \(a_1, a_2, \dots, a_n\) uzunlikdagi yog'och ustunlar mavjud. Olmaxon bu ustunlarning dastlabkisida turibdi, u oxirgi ustunga yetib borishi uchun minimal qancha enirgiya sarflaydi.

Agar olmaxon \(x_1\) - ustunda bo'lsa \(x_2\) - ustunga o'taoladi faqat \(\vert{}x_1 - x_2\vert{}\) enirgiya sarflaydi, olmaxon \(x_1\) - ustundan \(x_3\) - ustungaham o'taoladi faqat \(3 * \vert{}x_1 - x_3\vert{}\) enirgiya sarflaydi.

Misol, rasmda tasvirlangandek ustunlar berilgan bo'lsa olmaxon \(a_1\) ustundan \(a_2\) ustunga sakraydi \(\vert{}1 - 20\vert{} = 19\) va \(a_2\) dan \(a_4\) ga sakraydi \(3 * \vert{}20 - 22\vert{} = 6\), shunda olmaxon minimal enirgiyasi \(25\) ga teng bo'ladi.

Sizning vazifangiz olmaxon dastlabki ustundan oxirgi ustunga yetib borishi uchun minimal qancha enirgiya sarflashini aniqlashdan iborat.

Kiruvchi ma'lumotlar

Kirish faylining dastlabki satrida \(n\) (\(1 \le n \le 10^5\)) ustunlar soni va keyingi satrda \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6\)) ketma-ket ustun uzunliklari beriladi.

Chiquvchi ma'lumotlar

Chiqish faylida olmaxon dastlabki ustundan oxirgi ustunga yetib borishi uchun minimal qancha enirgiya sarflashini chop eting.

Misollar

1

4
1 20 7 22

25

2

5
1 2 100 3 4

5