WEIGHT  Weighted Sum
You are given N integers, A[1] to A[N]. You have to assign weights to these integers such that their weighted sum is maximized. The weights should satisfy the following conditions :
 Each weight should be an positive integer.
 W[1] = 1
 W[i] should be in the range [2, W[i1] + 1] for i > 1
Weighted sum is defined as S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]
Input
There are multiple test cases.
First line contains the number of test cases
Each test case consists of a single line containing N.
This is followed by N lines, each containing A[i]
Output
For each test case, output one line  the maximum weighted sum.
Example
Input:
1
4
1
2
3
4
Output: 6
Explanation
The weights are 1,2,3,2
Constraints
N <= 10^6
 A[i]  <= 10^6
Total number of test cases is around 10.
hide comments
DK...:
20190418 01:40:59
The solution is more clear reversing the array 

buttman:
20160727 17:15:11
@Shahbaz Khan Thanks, your commment helped.I almost gave up on finding a bug in my solution. 

ayush sinha:
20160219 12:10:33
please explain o(n) approach a bit


Sreejato Bhattacharya:
20150828 13:07:54
Nice problem!


Saksham :
20150707 00:18:46
think of kadane


Petar Nyagolov:
20141025 18:55:26
Can someone tell me how to solve it in O(n), please? 

Archit Jain:
20141025 15:38:41
working for all the test cases specified in the comment and the forum still wa plz help 

ISHANI:
20141002 07:07:48
awesome problem.No need for DP. 

kp:
20140914 20:09:59
Even with o(n)..got TLE..any suggestions?? 

Shahbaz Khan:
20140806 00:23:46
I got an O(n) solution, seems to be valid on all given and commented test cases. But still WA? And it does not need Fast IO. Am I doing it wrong?

Added by:  Kunal Jain 
Date:  20110207 
Time limit:  0.280s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  CodeCraft 11 