Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Baksis

Задача Baksis

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

 Технические условия

    Программа Baksis читает с клавиатуры число N (2≤N≤32 767), а далее 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


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"