30. Sum of All Odd Length Subarrays

Given an array arr of positive integers, return the sum of all possible odd-length subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

Input: An integer array arr of length n.

Output: Integer — sum of all odd-length subarrays.

Examples

Input: [1,4,2,5,3]
Output: 58
Explanation: Odd-length subarrays: [1]=1,[4]=4,[2]=2,[5]=5,[3]=3,[1,4,2]=7,[4,2,5]=11,[2,5,3]=10,[1,4,2,5,3]=15. Sum=1+4+2+5+3+7+11+10+15=58.

Input: [1,2]
Output: 3
Explanation: Odd-length subarrays: [1]=1,[2]=2. Sum=3.

Input: [10,11,12]
Output: 66
Explanation: [10]=10,[11]=11,[12]=12,[10,11,12]=33. Sum=66.

Constraints

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 1000

Asked by