Problem Description

$\rm Andrew$ is a very curious student. One day, he drew a circle on paper with its center at $(0,0)$. Let the circumference be $C$. The coordinates of each point on the circle are:

Now $\rm Andrew$ marks $n$ points on the circle. The $i$-th point is placed at $p_i$. $\rm Andrew$ may place multiple points at the same position.

A good triangle $(a,b,c)$ is defined as:

• $1 \le a < b < c \le n$.
• The origin $(0,0)$ lies strictly inside the triangle whose vertices are at $p_a$, $p_b$, and $p_c$. Note in particular that the origin is not on the boundary of the triangle.

$\rm Andrew$ asks you how many good triangles there are.

Input Format

The first line contains two integers $n, c$, representing the number of points and the circumference of the circle.

The next line contains $n$ integers. Their meaning is described above.

Output Format

Output an integer $x$, indicating that there are $x$ good triangles.

8 10
0 2 5 5 6 9 0 0

6

Hint

Explanation for Sample $1$:

$\rm Andrew$ drew the following figure:

The origin lies strictly inside the triangle with vertices at $p_1$, $p_2$, and $p_5$, so $(1,2,5)$ is a good triangle. The other five good triplets are $(2,3,6)$, $(2,4,6)$, $(2,5,6)$, $(2,5,7)$, and $(2,5,8)$.

For $20\%$ of the testdata: $3 \le n \le 200$, $3 \le c \le 10^6$.

For another $20\%$ of the testdata: $3 \le n \le 10^6$, $3 \le c \le 6000$.

For $40\%$ of the testdata: $3 \le n \le 10^6$, $3 \le c \le 10^6$, and all point positions are pairwise distinct.

For $100\%$ of the testdata: $3 \le n \le 10^6$, $3 \le c \le 10^6$.

Translated by ChatGPT 5