Maximum Product Subarray

Given an array of integers, find a contiguous subarray within the array (containing at least one number) which has the largest product. The product is defined as the multiplication of all the elements in that subarray.

Note that the array can contain positive numbers, negative numbers, and zeros. Be cautious as negative numbers and zeros can significantly affect the product. The goal is to find the maximum product obtainable from any contiguous segment of the array.

Mathematically, if we denote a subarray from index i to j by \(a_i, a_{i+1}, \ldots, a_j\), then you are to compute \[ \max_{0 \le i \le j < n} \prod_{k=i}^{j} a_k \]

inputFormat

The first line of input contains an integer n, denoting the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

Example:

4
2 3 -2 4

outputFormat

Output a single integer, the maximum product of all contiguous subarrays.

Example Output:

6

4
2 3 -2 4

6