Description

等差数列 指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，且这个常数叫做等差数列的公差。 例如：数列 1 5 9 13 就是一个公差为 4 的等差数列。 现给定一个长度为 n 的序列 a 1 , a 2 , . . . , a n ，请问该序列中，有多少个长度不小于 3的子段满足等差数列？

Format

Input

输入共两行： 第一行，一个正整数 n，表示给定序列长度 第二行，n 个整数，分别表示序列的每一项 a 1 , a 2 , . . . , a n

Output

输出一个整数，表示满足条件的子段个数。

Samples

10
-1 1 3 3 3 2 3 2 1 0

5

Limitation

1s, 1024KiB for each test case.对于 100 % 的数据， 1 ≤ n ≤ 10^5 , − 10^9 ≤ ai ≤ 10^9