Programmer Eugene visited Australia this summer. It turned out that in this
wonderful country one could not only watch kangaroos and emus, visit the world-famous
opera house, and swim in the warm sea, but also enjoy the unique
“Flying Pig Show,” which took place not far from Sidney. No wonder the show
attracts crowds of people: flying pigs with visible pleasure flop into a
pool. Before plunging into the water, they take a run and jump from a
platform fixed at a height of almost four meters above the water level. In
order to gape at the amazing pigs, the crowd gathers about an hour before the
start of the show.
After the performance, the organizers choose the most popular pig and present
a symbolic prize to it. The popularity of a pig is calculated on the basis of the
audience’s likings: each guest gives a mark (an integer not exceeding 3 in
absolute value) to each pig. Each pig’s marks are written as a sequence and then a
nonempty subsequence of consecutive numbers
is chosen in which the product of numbers is maximal. This
product is taken by the organizers as the popularity of the pig.
The show became so popular that the number of guests is very large.
That is why it is not always easy to choose the best pig. Eugene offered the organizers
his help in automating the process of calculating the popularities of pigs.
The first line contains the number of guests n at the “Flying Pig Show”
(1 ≤ n ≤ 50000).
The next line contains n integers, which are the guests’ marks for a pig,
in the order the organizers write them down.
Output the popularity of the pig.
Problem Author: Sergey Pupyrev
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007