Условие:
Однажды Ренат нашел массив целых чисел a
длины n
(элементы массива нумеруются с 1) и, так как он перфекционист, решил приукрасить его. Для этого он может провести ровно одну операцию следующего вида: выбрать два индекса l
и r
(1≤l≤r≤n
) и поменять знак у всех ai
, для которых выполнено условие l≤i≤r
. Красотой массива Ренат считает ∑i=2n|ai−ai−1|
, то есть |a2−a1|+|a3−a2|+…+|an−an−1|
.
Помогите Ренату узнать максимальную красоту массива a
, которую он может получить, выполнив ровно одну операцию.
Входные данные
Первая строка содержит одно целое число n
(2≤n≤2⋅105
) — количество элементов массива.
Вторая строка содержит n
целых чисел a1,a2,…,an
(−109≤ai≤109
) — массив a
.
Выходные данные
Выведите одно число — максимальную красоту массива, которую может получить Ренат.