Subarray Sum solution codechef

For Solution

Click Here!

Chef has a sequence of $N$ integers $A_{1}, A_{2}, \dots, A_{N}$ . He defines a function $f (i, j)$ as follows:

$f (i, j) = A_{i} + m a x (A_{i}, A_{i + 1}) + m a x (A_{i}, A_{i + 1}, A_{i + 2}) + \dots + m a x (A_{i}, A_{i + 1}, \dots, A_{j})$

Chef tries to find the sum of $f (i, j)$ over all $(i, j)$ such that $1 \leq i \leq j \leq N$ $(i . e \sum_{i = 1}^{n} \sum_{j = i}^{n} f (i, j))$ , but fails. Can you help him find the sum?

Subarray Sum solution codechef

Since the sum can be very large, find it modulo $(10^{9} + 7)$ .

Note: Since the size of the input and output is large, please use fast input-output methods.

Input Format

Subarray Sum solution codechef

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains an integer $N$ .
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format

Subarray Sum solution codechef

For each test case, print a single line containing one integer – the required sum i.e $\sum_{i = 1}^{n} \sum_{j = i}^{n} f (i, j)$ modulo $(10^{9} + 7)$ .

Constraints

$1 \leq T \leq 5 \cdot 10^{3}$
$1 \leq N \leq 2 \cdot 10^{5}$
$1 \leq A_{i} \leq 10^{9}$
Sum of $N$ over all test cases does not exceed $10^{6}$ .

Sample Input 1

Subarray Sum solution codechef

Sample Output 1

Subarray Sum solution codechef

6
20
82

Explanation

Test case $1$ :

$f (1, 1) = A_{1} = 1$ .
$f (1, 2) = A_{1} + m a x (A_{1}, A_{2}) = 1 + m a x (1, 2) = 1 + 2 = 3$ .
$f (2, 2) = A_{2} = 2$ .

Hence the required sum $= 1 + 3 + 2 = 6$ .

Test case $2$ :

$f (1, 1) = A_{1} = 1$ .
$f (1, 2) = A_{1} + m a x (A_{1}, A_{2}) = 1 + m a x (1, 2) = 1 + 2 = 3$ .
$f (1, 3) = A_{1} + m a x (A_{1}, A_{2}) + m a x (A_{1}, A_{2}, A_{3}) = 1 + m a x (1, 2) + m a x (1, 2, 3) = 1 + 2 + 3 = 6$ .
$f (2, 2) = A_{2} = 2$ .
$f (2, 3) = A_{2} + m a x (A_{2}, A_{3}) = 2 + m a x (2, 3) = 2 + 3 = 5$ .
$f (3, 3) = A_{3} = 3$ .

Hence the required sum $= 1 + 3 + 6 + 2 + 5 + 3 = 20$ .

For Solution

Click Here!

Subarray Sum solution codechef

For Solution

Click Here!

Subarray Sum solution codechef

Input Format

Subarray Sum solution codechef

Output Format

Subarray Sum solution codechef

Constraints

Sample Input 1

Subarray Sum solution codechef

Sample Output 1

Subarray Sum solution codechef

Explanation

For Solution

Click Here!

Leave a Comment Cancel Reply