Математические платформы
Математические платформы
В старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться с одного края экрана до другого. Игрок может прыгнуть с любой платформы i на любую платформу k, затратив при этом (i - k) * (i - k) * (y_i - y_k) * (y_i - y_k) единиц энергии, где y_i и y_k — высоты на которых расположены эти платформы. Конечно же, энергию следует расходовать максимально экономно.
Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?
Входные данные
В первой строке записано количество платформ n~(1 \le n \le 4000). Вторая строка содержит n целых чисел, не превосходящих по модулю 200000 — высоты, на которых располагаются платформы.
Выходные данные
Выведите единственное число — минимальное количество энергии, которое должен потратить игрок на преодоление платформ.
Пример
4 1 2 3 30
731