问题描述

小李是一名中二病患者，他拥有一个神秘的双刀流招式，可以向一个长度为 $n$ 的数组 $A$ 挥刀, $A = {A_1, A_2, .. A_n}$，将其 恰好 分割成三段 连续 的 非空子数组，将这三段非空子数组内的元素的和从左向右分别记为 $sum1$, $sum2$, $sum3$，则小陈，小樊，小魏会依次分别获得 $sum1$, $sum2$, $sum3$ 个糖果。但是，小陈、小樊和小魏对于自己获得的糖果数有着特别的要求。

小陈希望自己获得的糖果数是非负数，因为他相信只有积极向上的心态才能带来好运。小樊则希望自己获得的糖果的个数是小陈获得的糖果的个数的二次方，因为他相信只有强大的力量才能征服一切。而小魏则希望自己获得的糖果的个数是小樊获得的糖果的个数与小陈获得的糖果的个数的和，因为他相信只有和谐共处才能带来真正的幸福。 简单来说，若分别设小陈、小樊、小魏获得的糖果数为$sum1$, $sum2$, $sum3$, 则 $sum1$, $sum2$, $sum3$ 满足式子： $sum1 >= 0 , sum2 = (sum1)^2 , sum3 = sum2 + sum1$。

现在，小李需要你的帮助，计算出有多少种不同的分割数组的方式（即不同方案）可以满足他们仨的要求。

注意，两种方案被认为是不同的当且仅当分割位置至少有一处与之前有过的方案不同。

输入格式

第一行给出正整数 $n$ ，表示数组的长度。

第二行给出 $n$ 个数, 第 $i$ 个数代表 $A_i$。

输出格式

输出一个整数，表示不同的方案的数量。

输入样例

4
1 1 0 2

输出样例

2

评测数据规模

对于所有评测数据： $1 \le n \le 10^5$ , $-10^5 \le A_i \le 10^5$。

保证所有答案不超过 $2^{63}$

样例解释

可以将数组划分为 $[1,1] , [2,2], [3,4]$ 三段或划分为 $[1,1] , [2,3], [4,4]$ 三段 ，这两种情况下 $sum1 = 1 , sum2 = 1, sum3 = 2$ ，都满足题目条件。显然在该样例情况下只存在这两种方案，因此方案数为 $2$ 。