ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1587. Flying Pig

Time limit: 0.75 second
Memory limit: 64 MB
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.

Input

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

Output the popularity of the pig.

Sample

inputoutput
3
1 2 -1
2
Problem Author: Sergey Pupyrev
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007