645. Sum of All Odd Length Subarrays

0

Medium

Alice is fond of odd numbers and wants to determine the sum of all subarrays with odd lengths in a given array. She requires your assistance in solving this problem.
You are provided with an array of positive integers, arr. Calculate and print the sum of all possible subarrays with odd lengths in arr.
***Note: A subarray is a contiguous subsequence of the array.***

Input Format

The first line contains an integer N, representing the size of the array.
The second line contains the elements of the array.

Output Format

Print the sum of all possible subarrays with odd lengths in arr.

Example

Input

5
1 4 2 5 3

Output

58

Constraints

1 <= N <= 10000

-1000 <= nums[i] <= 1000

-1000 <= nums[i] <= 1000

Loading...

View Submissions

Console