Description

希蒙热爱大自然，并且很有公益心。每年暑假都会跑去沙漠植树造林。

到达今年，希蒙已经中了 $N$ 棵树（高低不同的树），编号为 $1...N(1 \leq N \leq 1500)$ ，排列成一行。树 $i$ 高度为 $p_i$ 厘米$(1 \le p_i \le 1000)$。

为了纪念希蒙的植树成果，希蒙决定给这些树拍些照片。具体地说，对于每一对满足 $1 \leq i \leq j \leq N$ 的树 $(i, j)$，希蒙会给从树 $i$ 到树 $j$ 之间的所有树(包括 $i$ 和 $j$)拍一张照。

后来希蒙再分享这些照片给蒙蒙看时，蒙蒙发现这些照片中有些照片里存在「平均」的树——一棵树的高度恰好是 $P$ 厘米，其中 $P$ 等于照片中所有树高度的平均值。

希蒙的照片中有几张存在平均的树？

Format

Input

输入的第一行包含 $N$。

输入的第二行包含 $N$ 个空格分隔的整数 $p_1...p_N$。

Output

输出存在平均的树的照片数量。

Samples

4
100 100 200 300

6

样例提示

每张仅包含一棵树的照片均会被计入答案（在这个样例中有 $4$ 张）。另外，在这个样例中 $(i, j)$ 为 $(1, 2)$ 和 $(2, 4)$ 所对应的照片也存在平均的树。