Problem D
Sum and Product
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).
Input
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
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 |
