Cho một dãy số $A=(a_1,a_2,\cdots,a_n)$, hỏi có bao nhiêu khoảng $[L,R]$ thỏa mãn tích các phần tử trong khoảng bằng tổng của chúng, tức là $a_L \cdot a_{L+1} \cdots a_R = a_L + a_{L+1} + \cdots + a_R$.

Dữ liệu vào

Dòng đầu tiên của input chứa một số nguyên n, biểu thị độ dài của dãy số. Dòng thứ hai chứa n số nguyên, lần lượt biểu thị các số trong dãy $a_1,a_2,\cdots,a_n$.

Dữ liệu ra

In ra đúng một dòng chứa một số nguyên, biểu thị số lượng khoảng thỏa mãn điều kiện trên.

Ví dụ

Input

4
1 3 2 2

Output

6

Ghi chú

Phạm vi dữ liệu

• $1 \leq n \leq 200000$
• $1 \leq a_i \leq 200000$