В Ужляндии опять что-то произошло... На улицах беспорядки... Для спасения ситуации было решено призвать знаменитых ужляндских героев — баранчика Шона и жирафика Стаса. По прибытию они обнаружили, что граждане обеспокоены незнанием крайних значений Главной Ужляндской Функции f, которая определяется следующим образом:
В этой формуле 1 ≤ l < r ≤ n, где n — размер Главного Ужлянжского Массива a, а |x| обозначает модуль числа x. Но герои прогуливали уроки математики, и поэтому они просят вашей помощи. Помогите им вычислить максимальное значение f среди всех допустимых значений l и r для заданного массива a.
Выходные данные
Выведите одно целое число — максимальное значение функции f.
Примечание
В первом примере максимальное значение f достигается на отрезках [1, 2] и [2, 5].
Во втором примере максимальное значение f достигается, только если отрезком является весь массив.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4 2 3 1
|
3
|
|
2
|
4
1 5 4 7
|
6
|