eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Платформы - 3

Платформы - 3

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит |y[2] - y[1]| ^2 энергии, где y[1] и y[2] - высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается 3 * |y[3] - y[1]| ^2 энергии. Через ^ здесь обозначено возведение в степень.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с 1-й платформы до n-й (последней).

Входные данные

Первая строка содержит количество платформ n (2n10^5), вторая - n целых чисел, значения которых не превышают по модулю 4000 - высоты платформ.

Выходные данные

Выведите единственное целое число - искомую величину энергии.

Пример

Входные данные #1
4
1 2 3 30
Выходные данные #1
731