Бэтмен и Робин

Подготовка нового Робина непростая задача, однако для Бэтмена нет ничего невозможного. Так как настоящий супергерой должен быть умным. Сегодня у Робина умственная тренировка.

Бэтмен дал непростую задачку: у Робина есть последовательность $a_1, a_2 \dots a_n$. По которой вычисляется следующая сумма: $\sum\limits_{i=1}^n(-1)^{i-1} \cdot a_i = a_1 - a_2 + a_3 - \dots$ То есть члены последовательности с нечетными индексами берутся со знаком <<плюс>>, а четные со знаком <<минус>>.

Робин может поменять ровно два числа местами один раз, чтобы итоговая сумма стала больше (а может и не менять, если и так все хорошо). Бэтмену нужно будет проверить ответ, но ему лень вычислять его вручную, поэтому он просит вас написать программу, которая посчитает, какую максимальную сумму может получить Робин из данной последовательности.

В первой строке входного файла содержится одно натуральное число $n$ --- количество чисел в последовательности ($2 \le n \le 10^{5}$).

Во второй строке входного файла дано $n$ чисел $a_i$ --- числа последовательности ($1 \le a_i \le 1000$).

В единственной строке выходного файла выведите ответ на задачу --- максимальную сумму может получить Робин из данной последовательности.

В первом примере изначальная сумма равна -1, но поменяв числа местами, можно получить 1. Во втором примере ничего не поменяется при смене, поэтому можно не менять числа местами вовсе.