Maximum Product Subarray

Given an array of n integers (where 1 \le n \le 10^4), find the maximum product of a contiguous subarray.

The array can contain both positive, negative and zero values. A subarray is defined as a contiguous part of the array. The key observation is that whenever a negative number is encountered, the maximum product so far may become the minimum product when multiplied by the negative number, and vice versa.

Formally, if we let \(a_i\) denote the i-th element of the array, we can define:

[ \text{max_so_far} = \max{a_i, \text{max_so_far} \times a_i, \text{min_so_far} \times a_i} ]

[ \text{min_so_far} = \min{a_i, \text{max_so_far(previous)} \times a_i, \text{min_so_far} \times a_i} ]

Your task is to compute the maximum product over all contiguous subarrays.

inputFormat

The input is given via standard input (stdin) in the following format:

First line: A single integer n denoting the number of elements in the array.
Second line: n space-separated integers denoting the elements of the array.

outputFormat

Output the maximum product of any contiguous subarray as a single integer to standard output (stdout).

## sample

4
2 3 -2 4

6