Problem Description
Let's the sum of the array S be sum(S) and the maximum be max(S). The cost of an array S is ceil(sum(S)/2) * max(S). ceil(x) is the smallest integer not less than x.
You have an array A of length N. Find the sum of the cost of all the subarrays of this array.
Since the answer can be large, return it modulo 109 + 7.
1 <= N <= 5 x 105
1 <= A[i] <= 106
The first and only argument contains an integer array A of length N.
Return the sum of cost of all subarrays modulo 109 + 7.
Input 1:
A : [ 1, 2 ]
Input 2:
A : [5]
Output 1:
7
Output 2:
15
Explanation 1:
The array has 3 subarrays- 1. [1] - Cost = 1 * ceil(1/2) = 1 2. [2] - Cost = 2 * ceil(2/2) = 2 3. [1, 2] - Cost = 2 * ceil(3/2) = 4 Sum of cost = 7
Explanation 2:
It has only one subarray. Cost is 5 * ceil(5/2) = 15
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.