Maximum Product Subarray

Given an array of integers, your task is to find the maximum product of any contiguous subarray. In other words, for the given integer sequence \(a_1, a_2, \dots, a_n\), determine the maximum value of the product:

\[ \max_{1 \le i \le j \le n} \; \prod_{k=i}^{j} a_k \]

This problem requires you to handle positive, negative, and zero values properly. Note that a subarray is defined as a contiguous segment of the array.

inputFormat

The input is read from standard input (stdin). The first line of the input contains a single integer (n) denoting the number of elements. The second line contains (n) space-separated integers representing the array elements.

outputFormat

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

1
3

3