Подготовка нового Робина непростая задача, однако для Бэтмена нет ничего невозможного. Так как настоящий супергерой должен быть умным. Сегодня у Робина умственная тренировка.
Бэтмен дал непростую задачку: у Робина есть последовательность a1, a2... an. По которой вычисляется следующая сумма: 
То есть члены последовательности с нечетными индексами берутся со знаком «плюс», а четные со знаком «минус».
Робин может поменять ровно два числа местами один раз, чтобы итоговая сумма стала больше (а может и не менять, если и так все хорошо). Бэтмену нужно будет проверить ответ, но ему лень вычислять его вручную, поэтому он просит вас написать программу, которая посчитает, какую максимальную сумму может получить Робин из данной последовательности.
В первой строке входного файла содержится одно натуральное число n — количество чисел в последовательности (2 ≤ n ≤ 105).
Во второй строке входного файла дано n чисел ai — числа последовательности (1 ≤ ai ≤ 1000).
В единственной строке выходного файла выведите ответ на задачу — максимальную сумму может получить Робин из данной последовательности.
Первая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 100. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 25 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 10 000. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 36 баллов.
Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 39 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».
2
1 2
1
3
2 2 2
2
В первом примере изначальная сумма равна -1, но поменяв числа местами, можно получить 1. Во втором примере ничего не поменяется при смене, поэтому можно не менять числа местами вовсе.