Интересная задачка, как её решать да и так, чтобы максимально эффективно?

Паркур Мальчик Миша профессионально занялся паркуром. Для своего показательного номера он нашел N стоящих в ряд столбов, высота i-го столба равна hi. Как известно, чем дальше и выше прыжок, тем он более крутой. Крутость прыжка со столба i на столб j оценивается формулой |i - j| + hj - hi. Миша должен начать на каком-то столбе, после чего посетить все столбы ровно один раз. Скажите Мише максимальную суммарную крутость прыжков.

Формат входных данных В первой строке вводится целое число N - число столбов (1 ≤ N ≤ 3000). Во сторой строке вводится N целых чисел hi - высоты столбов (1 ≤ hi ≤ 109).

Формат результата Выведите одно целое число - максимальную суммарную крутость прыжков.

Примеры Входные данные 4 1 2 3 1 Результат работы 8 Входные данные 5 2 1 5 4 5 Результат работы 15