You are given an array of positive integers,
. Let the value of an array be the number of trailing zeros in the product of all its elements. Determine the sum of the values of all subarrays of
.
Constraints
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
Input Specification
The first line contains one integer, , the length of the array.
The next line contains space-separated integers,
, the array of positive integers.
Output Specification
Output one line containing one integer, the sum of the values of all subarrays.
Note: This number may not fit within a 32-bit integer type.
Sample Input 1
5
3 1 4 1 5
Sample Output 1
3
Explanation for Sample 1
The only subarrays with a nonzero value are
,
, and
. The products of each subarray are
,
, and
, respectively. Each product has only
trailing zero, for a total value of
. All of the other subarrays have products with no trailing zeroes.
Sample Input 2
7
10 2 5 4 5 6 7
Sample Output 2
35
Comments
marcorz