Question
Total Sum of all Subarrays Sum
You are given an array of KaTeX can only parse string typed expression integers. Your task is to find the sum of all possible subarray sums of the array.
In other words, for every possible subarray of the array, compute its sum, and then find the total of all those subarray sums.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression.
Output
Print a single integer — the sum of all subarray sums of the given array.
Example
Input
3
1 2 3
Output
20
Explanation
All subarrays and their sums:
[1] → 1
[2] → 2
[3] → 3
[1, 2] → 3
[2, 3] → 5
[1, 2, 3] → 6
Total = 1 + 2 + 3 + 3 + 5 + 6 = 20
3
1 2 3
Output
20
Explanation
All subarrays and their sums:
[1] → 1
[2] → 2
[3] → 3
[1, 2] → 3
[2, 3] → 5
[1, 2, 3] → 6
Total = 1 + 2 + 3 + 3 + 5 + 6 = 20