K-Subarray

You will be given an array of length n. You need to divide the array in some part where length of every part will be exactly k. Firstly, you will take first k elements of the array for the 1st part, then the next k elements to the 2nd part and so on. If there is less than k elements remain after making some parts (possibly zero), we will not take these elements to any part. That means, we will not take the last (n mod k) elements to any part. Let’s call a part of k length as k-subarray.

So if the array is [2, 4, 6, 8, 5] of length n = 5 and k = 2, then after partition, there will be two 2-subarrys: [2, 4] and [6, 8]. Note that, we will not take the last element of that array to any of 2-subarrys.

Let’s define the scorek as the maximum total sum of a k-subarry among all k-subarrys of that array. In above subarrays, the maximum score is 6 + 8 = 14 which greater than 2 + 4 = 6.

You need to find $ \sum_{k = 1}^{n} score_{k} $, summation of scorek for all possible k (1 ≤ k ≤ n).

Input

The input will be followed by a single integer n (1 ≤ n ≤ 105). The next line will contain n integers, every integer will be in between 1 and 109.

Output

Print the summation of scorek for all possible k (1 ≤ k ≤ n) as described in problem statement.

Sample

Input	Output
5 2 4 6 8 5	79
For k = 1, 1-subarrys are: [2], [4], [6], [8] and [5]. Maximum sum among these subarrays is 8. For k = 2, 2-subarrys are: [2, 4] and [6, 8]. Maximum sum among these subarrays is 14. For k = 3, 3-subarrys are: [2, 4, 6]. Maximum sum among these subarrays is 12. For k = 4, 4-subarrys are: [2, 4, 6, 8]. Maximum sum among these subarrays is 20. For k = 5, 5-subarrys are: [2, 4, 6, 8, 5]. Maximum sum among these subarrays is 25. So, score1 + score2 + score3 + score4 + score5 = 8 + 14 + 12 + 20 + 25 = 79