Maximum Product Subarray

Given an array of integers, your task is to find the maximum product of any contiguous subarray. In other words, for an array (a_1, a_2, \ldots, a_n), you need to compute:

[ \max_{1 \leq i \leq j \leq n} {a_i \times a_{i+1} \times \cdots \times a_j} ]

Be aware that the array may contain positive numbers, negative numbers, and zeros which can reset the product. The challenge is to handle these cases efficiently.

inputFormat

The first line contains a single integer (N) denoting the number of elements in the array. The second line contains (N) space-separated integers representing the array.

outputFormat

Output a single integer that is the maximum product of any contiguous subarray from the given array.## sample

4
1 2 3 4

24