MAXSPPROD

You are given an array A containing N integers. The special product of each i^th integer in this array is defined as the product of the following:

1. LeftSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] and (i>j). If multiple A[j]'s are present in multiple positions, the LeftSpecialValue is the maximum value of j. Here LeftSpecialValue is the index j and not A[j].
2. RightSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] and (j>i). If multiple A[j]'s are present in multiple positions, the RightSpecialValue is the minimum value of j. Here RightSpecialValue is the index j and not A[j].

Write a program to find the maximum special product of any integer in the array. In other words you have to find the maximum for all i (0<i<n-1) of product of l and r such that l is the LeftSpecialValue and r is the RightSpecialValue of an index i.

Note that the array A is zero indexed.

NOTE: As the answer can be large, output your answer modulo 10⁹ + 7.

1 <= N <= 10⁵
1 <= A[i] <= 10⁹

First and only argument is an integer array A.

Return an integer denoting the maximum special product of any integer.

Input 1:

 A = [1, 4, 3, 4]

Input 2:

 A = [10, 7, 100]

Output 1:

 3

Output 2:

 0

Explanation 1:

 For A[2] = 3, LeftSpecialValue is 1 and RightSpecialValue is 3.
 So, the ans is 1*3 = 3.
 

Explanation 2:

 There is not any integer having maximum special product > 0. So, the ans is 0.