Maximum Subarray Product

Given an array of integers (which may include negative numbers and zeros), your task is to find the contiguous subarray within the array that has the largest product. A subarray is a contiguous part of the array and must contain at least one number.

Formally, if the input array is \(a_1, a_2, \dots, a_n\), you need to determine the maximum value of the product \(a_i \times a_{i+1} \times \cdots \times a_j\) for \(1 \le i \le j \le n\).

Note: The product can be very large. In particular, for an input where all elements are equal to 2 and there are 100,000 elements, the answer is \(2^{100000}\). When printing the answer, output the full decimal representation of the product.

inputFormat

The first line contains an integer \(n\) \( (1 \le n \le 10^5)\), the number of elements in the array. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\). Each \(a_i\) is an integer which can be positive, negative or zero.

outputFormat

Output a single line containing the maximum product (in decimal form) of any contiguous subarray.

## sample

5
2 3 -2 4 -1

48

</p>