• # For Solution

Chef has a sequence of NN integers A1,A2,,ANA1,A2,…,AN. He defines a function f(i,j)f(i,j) as follows:

f(i,j)=Ai+max(Ai,Ai+1)+max(Ai,Ai+1,Ai+2)++max(Ai,Ai+1,,Aj)f(i,j)=Ai+max(Ai,Ai+1)+max(Ai,Ai+1,Ai+2)+⋯+max(Ai,Ai+1,…,Aj)

Chef tries to find the sum of f(i,j)f(i,j) over all (i,j)(i,j) such that 1ijN1≤i≤j≤N (i.ei=1nj=inf(i,j))(i.e∑i=1n∑j=inf(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 (109+7)(109+7).

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

## Subarray Sum solution codechef

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains an integer NN.
• The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

## Subarray Sum solution codechef

For each test case, print a single line containing one integer – the required sum i.e i=1nj=inf(i,j)∑i=1n∑j=inf(i,j) modulo (109+7)(109+7).

### Constraints

• 1T51031≤T≤5⋅103
• 1N21051≤N≤2⋅105
• 1Ai1091≤Ai≤109
• Sum of NN over all test cases does not exceed 106106.

## Subarray Sum solution codechef

3
2
1 2
3
1 2 3
4
5 4 1 3


## Subarray Sum solution codechef

6
20
82


### Explanation

Test case 11:

• f(1,1)=A1=1f(1,1)=A1=1.
• f(1,2)=A1+max(A1,A2)=1+max(1,2)=1+2=3f(1,2)=A1+max(A1,A2)=1+max(1,2)=1+2=3.
• f(2,2)=A2=2f(2,2)=A2=2.

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

Test case 22:

• f(1,1)=A1=1f(1,1)=A1=1.
• f(1,2)=A1+max(A1,A2)=1+max(1,2)=1+2=3f(1,2)=A1+max(A1,A2)=1+max(1,2)=1+2=3.
• f(1,3)=A1+max(A1,A2)+max(A1,A2,A3)=1+max(1,2)+max(1,2,3)=1+2+3=6f(1,3)=A1+max(A1,A2)+max(A1,A2,A3)=1+max(1,2)+max(1,2,3)=1+2+3=6.
• f(2,2)=A2=2f(2,2)=A2=2.
• f(2,3)=A2+max(A2,A3)=2+max(2,3)=2+3=5f(2,3)=A2+max(A2,A3)=2+max(2,3)=2+3=5.
• f(3,3)=A3=3f(3,3)=A3=3.

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