Subarray Sum codechef 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 1≤i≤j≤N1≤i≤j≤N (i.e∑i=1n∑j=inf(i,j))(i.e∑i=1n∑j=inf(i,j)), but fails. Can you help him find the sum?

Subarray Sum solution codechef

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.

Input Format

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.

Output Format

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.

Sample Input 1

Subarray Sum solution codechef

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

Sample Output 1

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.

Leave a Comment