| Codeforces Round 407 (Div. 1) |
|---|
| Закончено |
В Ужляндии опять что-то произошло... На улицах беспорядки... Для спасения ситуации было решено призвать знаменитых ужляндских героев — баранчика Шона и жирафика Стаса. По прибытию они обнаружили, что граждане обеспокоены незнанием крайних значений Главной Ужляндской Функции 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 достигается, только если отрезком является весь массив.
