ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2000. Grand Theft Array V

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Совсем скоро в продаже появится долгожданная игра Grand Theft Array V! Что, вы не слышали о ней? Надо немедленно исправить это недоразумение!
Игровые действия в GTA V разворачиваются на одномерном массиве целых чисел. В игре участвуют два игрока, для каждого из которых задана стартовая позиция. Игроки совершают ходы по очереди. На каждом ходу игрок забирает число, написанное в его текущей ячейке, затем ставит туда ноль и переходит в смежную слева или справа ячейку (разумеется, игрок не может выходить за пределы массива). Два игрока могут в некоторый момент времени находиться в одной ячейке. Счёт игрока — это сумма всех набранных во время игры чисел. Игра заканчивается, когда во всех ячейках массива записаны нули.
А теперь вычислите, какое максимальное количество очков могут набрать первый и второй игроки (первый игрок, разумеется, ходит первым), если они играют оптимально, то есть стремятся максимизировать свой счёт, а если существует несколько вариантов сделать это, то стараются минимизировать счёт противника.

Исходные данные

В первой строке записано целое число n — размер массива (10 ≤ n ≤ 105). Во второй строке записаны n целых чисел — исходный массив. Все элементы массива неотрицательны и не превосходят 10 000. В третьей строке записаны два целых числа — стартовые позициии первого и второго игроков соответственно. Индексация ячеек массива начинается с единицы.

Результат

Выведите два числа — счёт первого и второго игроков при оптимальной игре обоих.

Пример

исходные данныерезультат
10
1 2 3 4 5 6 7 8 9 0
4 8
21 24
Автор задачи: Илья Кучумов (подготовка — Кирилл Девяткин)
Источник задачи: Уральская региональная командная олимпиада по программированию 2013