Sum=Product

Time limit1sMemory limit1024 MB

Summary

Count the contiguous subarrays whose element sum equals their element product, for N up to 300,000 and each A_i up to 300,000.

Level: Medium6 of 10
Topics: Math, Brute force, Two pointers
Solved: No attempts yet

Problem

A sequence of length $N$ , $A_1, \cdots, A_N$ , is given. Count the integer pairs $(i, j)$ that satisfy all of the following conditions.

$1 \le i \le j \le N$
$A_i + A_{i+1} + \cdots + A_j = A_i \times A_{i+1} \times \cdots \times A_j$

Input

The first line contains the length $N$ of the sequence. ( $1 \le N \le 300\,000$ ) The second line contains $N$ integers $A_1, \cdots, A_N$ , separated by spaces. ( $1 \le A_i \le 300\,000$ )

Output

Print the number of integer pairs $(i, j)$ that satisfy the condition.

Examples1

Example 1
Input
```
6
3 1 2 4 1 5
```
Expected output
```
8
```