Боб придумал логическую игру "Пат и Паташон". В этой игре на виртуальной сцене находится nn персонажей

Боб придумал логическую игру "Пат и Паташон". В этой игре на виртуальной сцене находится nn персонажей различного роста, которые выстроены в один ряд. Игрок может удалить часть персонажей со сцены, при этом оставшиеся персонажи смыкаются, не изменяя своего взаимного расположения. После этого персонажи на сцене разбиваются на пары: первый со вторым, третий с четвертым, пятый с шестым и так далее. В момент удаления игрок должен позаботится о том, чтобы количество оставшихся персонажей стало четным. Первого персонажа в паре (с нечетным номером) будем называть Патом, а второго (с четным номером) — Паташоном. Эффектностью пары будем назвать разность роста Пата и Паташона. Эффектность может быть отрицательной, если окажется, что Пат ниже, чем Паташон. За один раунд игрок получает количество очков, равное сумме эффектностей всех пар. Игрок может удалить со сцены всех персонажей. В этом случае он получит ноль очков.

Рассмотрим пример. Пусть на сцене изначально находилось девять персонажей, рост которых задается массивом чисел (120,160,180,160,120,110,150,170,100)(12 0,160,180,160,120,110,150,170,100). Игрок удалил со сцены первого второго и седьмого персонажа. На сцене осталось шесть персонажей с ростом (180,160,120,110,170,100)(180,160,120,11 0,170,100). Они разбились на три пары (180,160),(120,110),(170,100)(180,160),( 120,110),(170,100);, при этом эффектность первой пары — 20, второй — 10, третей — 70. Таким образом, за такое разбиение на пары игрок получит 100 очков. Однако, если игрок оставит на сцене четырех персонажей с ростом (180,110,170,100)(180,110,170,100), то он получит 140 очков.

Напишите программу, которая посчитает максимальное количество очков, которые может получить игрок, для заданной последовательности персонажей.
Формат входных данных

На вход в первой строке подается одно натуральное число nn — количество персонажей на сцене в начале игры, 1≤n≤10001≤n≤1000. Далее в одной строке через пробел записана последовательность из nn натуральных чисел, которые задают рост персонажей. Числа не превосходят 1000.
Формат выходных данных

Выведите одно целое число — максимальное количество очков, которое может получить игрок для заданной последовательности персонажей.
Методика проверки

Программа проверяется на 15 тестах.

Sample Input:

9
120 160 180 160 120 110 150 170 100

Sample Output:

140

0