Задача Baksis

    В абсолютно нам чужій і жахливо корумпованій країні бригада з N старателів мила золото, причому кожен зсипав видобуток у свій мішечок. Бригадир, щоб Чесна Влада Країни закрили очі на їх витівки, велів підготувати 2 хабарі – Великому Столичному Босові (ВСБ) і Маленькому Місцевому Цареві (ММЦ). Хитрий Бригадир знав, скільки грамів золота намив кожен із старателів. Він вишикував їх у шеренгу, а потім, керуючись Вищими Міркуваннями, пройшов уздовж шеренги від початку до кінця, вказуючи пальцем на тих, хто повинен із неї вийти, а таких в будь-якому випадку буде не менше 2-х. Той, що вийшов першим, зробив крок вперед, а другий – назад, третій – знову вперед, четвертий – знову назад... У будь-якому випадку кількість тих, хто робив крок вперед, дорівнює кількості тих, хто робив крок назад. Зрозуміло, що кожен наступний із тих, хто виходить, стояв спочатку в шерензі правіше тих, які вийшли раніше.
    Далі Хитрий Бригадир велів «переднім» віддати свій видобуток для хабара Великому Столичному Босові, а «заднім» - Маленькому Місцевому Цареві. І ось тут-то і стали зрозумілими Вищі Міркування: різниця між сумами грамів золота, що йдуть на хабарі Великому Столичному Босові і Маленькому Місцевому Цареві, має бути максимальною. Допоможіть Хитрому Бригадирові реалізувати Вищі Міркування.

 Технічні умови

   Програма Baksis читає з клавіатури число N (2 ≤ N≤ 32767), а далі P₁, P₂, ..., P_N (1≤P_i ≤ 100 000) цілих чисел, де P_i – видобуток старателя, що стоїть в шерензі на і-му місці. Шеренга нумерується від лівого краю, починаючи з одиниці. Всі числа розділені пропусками.
    Програма виводить на екран одне число – максимально можливу різницю між хабарами.

  Приклади

Введення
 2    10000   1
Виведення
 9999

Введення
7  7  6  2  4  8  1  5
Виведення
12

Введення
4  1  2  3  4
Виведення
-1