Sum of Subarray Minimums

You are given an array A consisting of N integers. Your task is to find the sum of the minimum element of every contiguous subarray of A. Since the answer can be very large, output it modulo \(10^9+7\).

For each element \(A[i]\) in the array, consider the number of subarrays for which \(A[i]\) is the minimum. This can be computed using the formula:

[ \text{Contribution of } A[i] = A[i] \times (i - L_i) \times (R_i - i), ]

where \(L_i\) is the index of the previous smaller element (or -1 if none exists) and \(R_i\) is the index of the next smaller element (or N if none exists). The final answer is the sum of contributions of all elements taken modulo \(10^9+7\>.

This problem requires efficient computation, as a naive solution may run in \(O(N^2)\). Use a stack to efficiently compute the previous and next smaller elements for each index.

inputFormat

The first line contains an integer \(T\) representing the number of test cases.

For each test case, the first line contains an integer \(N\) denoting the size of the array. The next line contains \(N\) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line containing one integer — the sum of the minimums of all subarrays of the array modulo \(10^9+7\).

## sample

2
3
1 2 3
4
4 3 2 1

10
20

</p>