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

После окончания шоу организаторы выбирают самую популярную свинью и вручают ей символический приз — «Пятачок в небесах». Популярность вычисляется на основе зрительских симпатий: каждый посетитель ставит хрюшке оценку (целое число, по модулю не превосходящее 3). Выставленные оценки выписываются в ряд, после чего из них выбирается непустая подпоследовательность идущих подряд оценок с максимальным значением их произведения. Произведение чисел в этой подпоследовательности организаторы называют популярностью свиньи.

К сожалению, выбрать лучшую чудо-хрюшку не всегда просто — популярность шоу так возросла, что народу на «Летающей свинье» собирается очень много. Женя вызвался помочь организаторам и автоматизировать процесс вычисления популярности свиньи по выставленным оценкам.

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

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