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

1587. Летающая свинья

Ограничение времени: 0.75 секунды
Ограничение памяти: 64 МБ
Программист Женя этим летом отдыхал в Австралии. Оказалось, что там можно не только поглазеть на кенгуру и эму, побывать в известном на весь мир оперном театре и искупаться в теплом море, но и посетить уникальное шоу, проходящее недалеко от Сиднея — «Шоу Летающей свиньи». Шоу привлекает толпы любопытных. Еще бы: летающие свиньи с видимым удовольствием плюхаются в бассейн. Прежде чем погрузиться в воду, они разгоняются и прыгают с платформы, закрепленной на высоте почти 4 метра от уровня бассейна. Для того, чтобы поглазеть на чудо-поросят, толпа собирается примерно за час до начала представления.
После окончания шоу организаторы выбирают самую популярную свинью и вручают ей символический приз — «Пятачок в небесах». Популярность вычисляется на основе зрительских симпатий: каждый посетитель ставит хрюшке оценку (целое число, по модулю не превосходящее 3). Выставленные оценки выписываются в ряд, после чего из них выбирается непустая подпоследовательность идущих подряд оценок с максимальным значением их произведения. Произведение чисел в этой подпоследовательности организаторы называют популярностью свиньи.
К сожалению, выбрать лучшую чудо-хрюшку не всегда просто — популярность шоу так возросла, что народу на «Летающей свинье» собирается очень много. Женя вызвался помочь организаторам и автоматизировать процесс вычисления популярности свиньи по выставленным оценкам.

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

В первой строке находится количество зрителей, собравшихся на шоу n (1 ≤ n ≤ 50000). Следующая строка содержит n целых чисел — выставленные зрителями оценки.

Результат

Выведите единственное число — популярность свиньи.

Пример

исходные данныерезультат
3
1 2 -1
2
Автор задачи: Сергей Пупырев
Источник задачи: ACM ICPC 2007–2008. NEERC. Восточный подрегион. Екатеринбург, 27 октября 2007 г.