Largest product of a stretch

Problem

Nikhil is testing a game where each level changes the score multiplier. Level i multiplies the score by a[i], which can be negative or zero.

He may play any stretch of levels that are next to each other, with at least one level. Print the largest product of the numbers in such a stretch.

Input: The first line has one integer n. The second line has n integers: a[1] to a[n].
Output: One integer: the largest product.
Constraints: 1 ≤ n ≤ 2 × 10^4
-10 ≤ a[i] ≤ 10
The product of every stretch fits in a 64-bit long.

Example 1

Input

4
2 3 -2 4

Output

The stretch 2 3 gives 6. Any stretch with the -2 is negative.

Example 2

Input

3
-2 3 -4

Output

The whole line gives 24, because the two negatives cancel out.

Try the problem first. Open one hint at a time.

Hint 1

A negative number turns the largest product into the smallest one, and the smallest into the largest.

Hint 2

So for each position i keep two values: the largest and the smallest product of a stretch that ends at i.

Hint 3

Each of them is the best of three choices: a[i] alone, a[i] times the largest before it, or a[i] times the smallest before it.

Hint 4

The answer is the largest "ends here" value over every position. Start it from a[1], not from 0.

Write your Java code, run it on the examples and submit it to hidden tests.