Maximum Product Subarray

Given an array of integers, find the contiguous subarray within the array (containing at least one number) which has the largest product.

The problem requires you to output the maximum product obtainable from any contiguous subarray of the given list.

Mathematically, if the array is \(a_1, a_2, \dots, a_n\), you need to compute \(\max_{1 \leq i \leq j \leq n} \prod_{k=i}^{j} a_k\).

Note: The input is provided via standard input and the result should be printed to standard output.

inputFormat

The first line of input contains a single integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers representing the array \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer, which is the maximum product of a contiguous subarray within the given array.

5
1 2 3 4 5

120