Velma and Triplets

4.2

23 votes
Ad-Hoc, Combinatorics, Easy, Implementation, Math
Problem

Given an array of size N, Velma give Scooby and Shaggy to compute the following sum on the array (0-indexed array).
enter image description here,
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

  • 1N100,1arri1000 in 40% of test cases.
  • 1N3105,1arri5104 in 60% of test cases.

Note: The answer will fit in signed 64-bit integer

Sample Input
5
1 2 1 7 3
Sample Output
6
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.

Editor Image

?