Velma and Triplets
Problem
Given an array of size N, Velma give Scooby and Shaggy to compute the following sum on the array (0-indexed array).
,
where ⌊.⌋ is the floor operator.
Since it was taking too long for Scooby and Shaggy to compute the sum, they need your help.
Can you help them?
Input
The first line of input will contain a single integer N, denoting the size of the array.
The second line will contain N integers arr0, arr1, arr2, ..., arrn-1.
Output
Print a single integer, the answer to Velma's question.
Constraints
- 1≤N≤100,1≤arri≤1000 in 40% of test cases.
- 1≤N≤3⋅105,1≤arri≤5∗104 in 60% of test cases.
Note: The answer will fit in signed 64-bit integer
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
The following triplets exists in the given array:
1 2 1
1 2 7
1 2 3
1 1 7
1 1 3
1 7 3
2 1 7
2 1 3
2 7 3
1 7 3
So, if we compute the required sum using these triplets, we get the sum to be equal to 6.
