Counting Equilateral Triangles

$N$ points lie on a circle. Write a program that counts the distinct equilateral triangles whose three vertices are all among the given points.

The positions of the points are fixed by the arc lengths between neighboring points along the circle. In the figure below, (a) shows eight points whose consecutive arc lengths are 4, 2, 4, 2, 2, 6, 2, 2, and (b) shows the two equilateral triangles that can be built from them.

The first line contains the number of points $N$. The second line contains $N$ integers $X_1, X_2, \dots, X_N$. For $1 \le i \le N-1$, $X_i$ is the length of the arc between point $i$ and point $i+1$, and $X_N$ is the length of the arc between point $N$ and point $1$. Points $1$ through $N$ are numbered in one direction around the circle.

Restrictions

• $3 \le N \le 10^5$
• $1 \le X_i \le 10^3$ for $1 \le i \le N$

Print one line containing a single integer, the number of distinct equilateral triangles whose vertices are given points.