Гірський хребет

Ви знаходитесь перед гірським хребтом, що складається з $n$ частин. Висота $i$-ї частини дорівнює $a_i$. За допомогою джет-паку ви можете перелетіти з частини $i$ до частини $j$, витративши $|i-j|\cdot |a_i-a_j|$ енергії.

Оскільки краса хребта дуже заворожує, ви хочете відвідати кожну частину хребта. Визначіть мінімальну кількість енергії, якої буде достатньо для того, щоб відвідати кожну частину хребта. Зверніть увагу, що ви можете відвідувати одну й ту саму частину хребта декілька разів. Початково ви знаходитесь на першій частині хребта.

Input

Перший рядок мiстить одне цiле число $n$ ($1\le n\le 10^5$) — кількість частин гірського хребта.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 18$) — висоти кожної частини хребта.

Output

Виведiть одне цiле число — мінімальну кількість енергії.

Examples

Scoring

У цій задачі оцінювання буде відбуватися в інший спосіб. Тут будуть "блоки". Ви отримаєте певну кількість балів, лише якщо ваш розв'язок буде проходити усі тести відповідного блоку. Зверніть увагу, що якщо ваш розв'язок пройде усі тести онлайн блоку, то це не гарантуватиме те, що він пройде усі тести секретного блоку. Іншими словами, якщо ви отримаєте $25$ балів, то не гарантується, що ви отримаєте $50$ балів, ви гарантовано отримаєте лише $25$ балів.

Знизу описані блоки. Кількість балів за цей блок та додаткові обмеження, які виконуються у цьому блоці.

1. ($20\%$ балів) $1\le n\le 9$;

2. ($8\%$ балів) $1\le n\le 18$;

3. ($16\%$ балів) $1\le n\le 1000,1\le a_i\le 9$;

4. ($12\%$ балів) $1\le n\le 10^5,1\le a_i\le 9$;

5. ($28\%$ балів) $1\le n\le 1000$;

6. ($16\%$ балів) $1\le n\le 10^5$;