A. Снова функционалка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Ужляндии опять что-то произошло... На улицах беспорядки... Для спасения ситуации было решено призвать знаменитых ужляндских героев — баранчика Шона и жирафика Стаса. По прибытию они обнаружили, что граждане обеспокоены незнанием крайних значений Главной Ужляндской Функции f, которая определяется следующим образом:

В этой формуле 1 ≤ l < r ≤ n, где n — размер Главного Ужлянжского Массива a, а |x| обозначает модуль числа x. Но герои прогуливали уроки математики, и поэтому они просят вашей помощи. Помогите им вычислить максимальное значение f среди всех допустимых значений l и r для заданного массива a.

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

В первой строке входного файла единственное число n (2 ≤ n ≤ 105) — размер массива a.

Во второй строке n целых чисел a1, a2, ..., an (-109 ≤ ai ≤ 109) — элементы массива.

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

Выведите одно целое число — максимальное значение функции f.

Примеры
Входные данные
5
1 4 2 3 1
Выходные данные
3
Входные данные
4
1 5 4 7
Выходные данные
6
Примечание

В первом примере максимальное значение f достигается на отрезках [1, 2] и [2, 5].

Во втором примере максимальное значение f достигается, только если отрезком является весь массив.