Задачи
Компьютерная игра - квадратичные прыжки
Компьютерная игра - квадратичные прыжки
Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем трудностей при решении этой задачи это создать не должно.
Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой нибуть герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться с одного края экрана до другого. При этом, при прыжке с одной платформы на соседнюю, у героя уходит \textbf{|y_2-y_1|^2} энергии, где \textbf{y_2} и \textbf{y_1} - высоты, на которых расположены эти платформы. Кроме того у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается \textbf{3·|y_2-y_1|^2} единиц энергии. Конечно же, энергию следует расходовать максимально экономно.
Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?
\InputFile
В первой строке записано количество платформ \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{100000}). Вторая строка содержит \textbf{n} натуральных чисел, не превосходящих \textbf{4000} - высоты, на которых располагаются платформы.
\OutputFile
Выведите единственное число - минимальное количество энергии, которое должен потратить игрок на преодоление платформ (конечно же в предположении, что \textit{cheat-коды} использовать нельзя).
Входные данные #1
4 1 2 3 30
Выходные данные #1
731