Description

年轻的程序员Orange有一个梦想，那就是驾驶飞船穿越浩瀚的星海。他得到了一张古老的星图，上面标记着一条由n个“能量节点”组成的线性星际航道。每个节点 $i$ 都有一个独特的能量值 $a_i$。

Orange的飞船引擎有一种特殊的“能量回廊”模式，可以让他进行一次完美的短途跃迁。一次完美的跃迁需要满足以下条件：

1. 选择一个长度至少为3的连续航道区间 $[l, r]$ 作为跃迁路径。
2. 跃迁的起点节点 $l$ 和终点节点 $r$ 的能量类型必须相同（即 $a_l = a_r$）。
3. 启动跃迁需要消耗 $a_l$ 单位的能量。为了维持能量守恒，路径中所有中间节点（即 $l+1$ 到 $r-1$）提供的能量总和必须正好等于这次消耗的能量。

现在，Orange想知道，在这张星图上，总共存在多少条可以进行完美跃迁的路径。请你帮助他计算出这个数量。

Format

Input

第一行输入一个整数 $n (1 ≤ n ≤ 1e5)$，表示能量节点的数量。 第二行输入 $n$ 个整数 $a_i (-1e9 ≤ a_i ≤ 1e9)$，表示每个节点的能量值。

Output

输出一个整数，表示可以进行完美跃迁的路径总数。

Samples

5
9 3 3 3 9

2

6
-4 4 0 0 -8 -4

1

Note

对于第一个样例，可能的完美跃迁为：$[9,3,3,3,9]$和$[3,3,3]$。