Задачи
Платформы - 3
Платформы - 3
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_2 - y_1|^2$ энергии, где $y_1$ и $y_2$ --- высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3 \cdot |y_3 - y_1|^2$ энергии.
Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой (начальной) платформы до $n$-ой (последней).
\InputFile
Первая строка содержит количество платформ $n~(2 \le n \le 10^5)$. Вторая строка содержит $n$ целых чисел --- высоты платформ. Их значения не превышают по модулю $4000$.
\OutputFile
Выведите одно целое число --- искомую величину энергии.
Входные данные #1
4 1 2 3 30
Выходные данные #1
731