Задача 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