题目描述

给定一个数列 $A = (a_1, a_2, …… , a_n)$，问有多少个区间 $[L, R]$ 满足区间内元素的乘积等于他们的和，即 $a_L ·a_{L+1} …… a_R = a_L + a_{L+1} + …… + a_R$。

输入描述

输入第一行包含一个整数 $n$，表示数列的长度。

第二行包含 $n$ 个整数，依次表示数列中的数 $a_1, a_2, …… , a_n$。

输出描述

输出仅一行，包含一个整数表示满足如上条件的区间的个数。

4
1 3 2 2

6

样例解释

符合条件的区间为 $[1, 1], [1, 3], [2, 2], [3, 3], [3, 4], [4, 4]$。

评测用例规模与约定

对于 20% 的评测用例，$n \leq 3000$；

对于 50% 的评测用例，$n \leq 20000$；

对于所有评测用例，$1 \leq n \leq 200000, 1 \leq a_i \leq 200000$。