All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Remove the element
/

Algorithms, Easy-Medium, Greedy algorithm

Problem
Editorial
Analytics

You are given an integer array A of size N. You can perform an operation exactly N number of times. In the operation, you can remove one element from the array A and the operation will cost \(A_i\) units if \(i^{th}\) is removed from the array. The operation will take 1 second.

Elements of array A will keep on increasing every second until it is removed. Let \(i^{th}\) element is \(A_i\) at \(j^{th}\) second. Then the \(i^{th}\) element will increase by \((j + 1) * A_i\) and the element will become \(A_i + (j+1) * A_i\) at \((j+1)^{th}\) second.

Your task is to find the minimum cost to remove all the elements from the array A. As the answer can be very large, print the answer module \(10^9 + 7\).

Input Format
The first line of input contains a single integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of elements in the array A.
The second line of each test case contains N space-separated integers, \(i^{th}\) integer denotes \(A_i\).

Output Format
Print the answer corresponding to each test case in new line.

Constraints

  • \(1 \le T \le 10\)
  • \(1 \le N \le 10^5\)
  • \(1 \le A_i \le 10^9\)
SAMPLE INPUT
1
2
3 3
SAMPLE OUTPUT
9
Explanation

Initially, \(j = 0\)
The cost of removing the first element is 3 and it will take 1 second.
After 1 second, the second element will become \((j+1) * A_2 + A_2 = 1 * 3 + 3 = 6\) and j will become 1.
The cost of removing second element will be 6.
Total cost = \(3 + 6 = 9\)

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?