Sum and Product

Photo by
Skitterphoto

Sarah and Patricia are young, very gifted sisters. Ever since they learned arithmetic in preschool, they have been bothering their mother Marguerite day and night to practice their calculations. Marguerite bought the two girls an arithmetic practice book, which has $n$ pages and a positive integer on each page. Those integers can be used for practicing arithmetic calculations. Marguerite hopes that the book can keep the two girls busy for a while so that she can work on her other chores.

Sarah and Patricia need to know whether their calculated
answers are right, but Marguerite does not have the time to
check their work. She therefore comes up with the clever idea
of *adversarial toddler training*. Marguerite
knows that Sarah is good at addition and Patricia is talented
in multiplication. So she first chooses a range of consecutive
book pages (at least two), and then asks Sarah to calculate the
sum of the integers on these pages, and asks Patricia to
calculate the product of these integers. If she chooses the
pages carefully, then the two girls’ answers would be the same,
and she can simply let Sarah and Patricia compare their
answers!

As Sarah and Patricia do not want to practice on the same range multiple times, Marguerite wants to know in how many different ways she can select a range of pages for her toddler training (and when to buy a new practice book).

The input has a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) on the first line. The second line has $n$ positive integers giving the numbers in the arithmetic practice book ordered by the pages. None of these integers are larger than $10^9$.

Output a single integer, the number of ways for Marguerite to choose a range of at least two consecutive pages so that Sarah’s answer matches Patricia’s.

Sample Input 1 | Sample Output 1 |
---|---|

5 2 2 1 2 3 |
2 |

Sample Input 2 | Sample Output 2 |
---|---|

8 1 2 4 1 1 2 5 1 |
4 |

Sample Input 3 | Sample Output 3 |
---|---|

4 5 6 7 8 |
0 |