Ренат нашел массив целых чисел a длины n (элементы массива нумеруются с 1). Он может провести ровно одну операцию: выбрать два индекса l и r (1 ≤ l ≤ r ≤ n) и поменять знак у всех a_i, для которых выполнено условие l ≤ i ≤ r. Красотой массива Ренат

Однажды Ренат нашел массив целых чисел 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
.

Выходные данные
Выведите одно число — максимальную красоту массива, которую может получить Ренат.