Given an array of size N, Velma give Scooby and Shaggy to compute the following sum on the array (0-indexed array).
,
where \(\lfloor.\rfloor\) 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 arr₀, arr₁, arr₂, ..., arr_n-1.

Output

Print a single integer, the answer to Velma's question.

Constraints

• \( 1 \leq N \leq 100, 1 \leq arr_{i} \leq 1000 \) in 40% of test cases.
• \( 1 \leq N \leq 3 \cdot 10^5, 1 \leq arr_{i} \leq 5*10^4 \) in 60% of test cases.

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