Maximum Product Subarray

Given an array of integers, your task is to find the contiguous subarray within the given array (containing at least one number) that has the largest product. The array may contain positive numbers, negative numbers, or zeros. A careful tracking of both the maximum and minimum products is necessary since multiplying by a negative number reverses the roles of these values.

For an array \(A = [a_1, a_2, \dots, a_n]\), the goal is to compute:

\[ max\_product = \max_{1 \leq i \leq j \leq n} \prod_{k=i}^{j} a_k \]

Input is provided via standard input (stdin) and output should be written to standard output (stdout).

inputFormat

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

outputFormat

Output a single integer which is the largest product of a contiguous subarray.## sample

4
2 3 -2 4

6

</p>