You are given an array of ~N~ positive integers, ~a_1, a_2, \dots a_N~. 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 ~a~.

Constraints

~1 \le N \le 5 \times 10^5~
~1 \le a_i \le 10^9~

Subtask 1 [20%]

~1 \le N \le 5\,000~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains one integer, ~N~, the length of the array.

The next line contains ~N~ space-separated integers, ~a_1, a_2, \dots, a_N~, 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 ~3~ subarrays with a nonzero value are ~[4,1,5]~, ~[1,4,1,5]~, and ~[3,1,4,1,5]~. The products of each subarray are ~20~, ~20~, and ~60~, respectively. Each product has only ~1~ trailing zero, for a total value of ~1 + 1 + 1 = 3~. 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