Задача Baksis
В абсолютно нам
чужій і жахливо корумпованій країні бригада з N старателів мила
золото, причому кожен зсипав видобуток у свій мішечок. Бригадир, щоб
Чесна Влада Країни закрили очі на їх витівки, велів підготувати 2 хабарі
– Великому Столичному Босові (ВСБ) і Маленькому Місцевому Цареві (ММЦ).
Хитрий Бригадир знав, скільки грамів золота намив кожен із старателів.
Він вишикував їх у шеренгу, а потім, керуючись Вищими Міркуваннями,
пройшов уздовж шеренги від початку до кінця, вказуючи пальцем на тих,
хто повинен із неї вийти, а таких в будь-якому випадку буде не менше
2-х. Той, що вийшов першим, зробив крок вперед, а другий – назад, третій
– знову вперед, четвертий – знову назад... У будь-якому випадку
кількість тих, хто робив крок вперед, дорівнює кількості тих, хто робив
крок назад. Зрозуміло, що кожен наступний із тих, хто виходить, стояв
спочатку в шерензі правіше тих, які вийшли раніше.
Далі Хитрий Бригадир велів «переднім» віддати свій видобуток
для хабара Великому Столичному Босові, а «заднім» - Маленькому Місцевому
Цареві. І ось тут-то і стали зрозумілими Вищі Міркування: різниця між
сумами грамів золота, що йдуть на хабарі Великому Столичному Босові і
Маленькому Місцевому Цареві, має бути максимальною. Допоможіть Хитрому
Бригадирові реалізувати Вищі Міркування.
Технічні умови
Програма Baksis читає з клавіатури
число N (2 ≤ N≤ 32767), а далі P1, P2,
..., PN (1≤Pi ≤ 100 000) цілих чисел, де Pi
– видобуток старателя, що стоїть в шерензі на і-му
місці. Шеренга нумерується від лівого краю, починаючи з одиниці. Всі
числа розділені пропусками.
Програма виводить на екран одне число – максимально можливу
різницю між хабарами.
Приклади
Введення
2 10000 1
Виведення
9999
Введення
7 7 6 2 4 8 1 5
Виведення
12
Введення
4 1 2 3 4
Виведення
-1