CCC '22 S4 - Good Triplets

Canadian Computing Competition: 2022 Stage 1, Senior #4

Andrew is a very curious student who drew a circle with the center at $(0, 0)$ and an integer circumference of $C \ge 3$. The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.

Andrew drew $N \ge 3$ points at integer locations. In particular, the $i^\text{th}$ point is drawn at location $P_i$ ($0 \le P_i \le C - 1$). It is possible for Andrew to draw multiple points at the same location.

A good triplet is defined as a triplet $(a, b, c)$ that satisfies the following conditions:

• $1 \le a < b < c \le N$.
• The origin $(0, 0)$ lies strictly inside the triangle with vertices at $P_a$, $P_b$, and $P_c$. In particular, the origin is not on the triangle's perimeter.

Lastly, two triplets $(a, b, c)$ and $(a', b', c')$ are distinct if $a \ne a'$, $b \ne b'$, or $c \ne c'$.

Andrew, being a curious student, wants to know the number of distinct good triplets. Please help him determine this number.

Input Specification

The first line contains the integers $N$ and $C$, separated by one space.

The second line contains $N$ space-separated integers. The $i^\text{th}$ integer is $P_i$ ($0 \le P_i \le C - 1$).

The following table shows how the available $15$ marks are distributed.

Output Specification

Output the number of distinct good triplets.

Sample Input

Sample Output

Explanation

Andrew drew the diagram above. The origin lies strictly inside the triangle with vertices $P_1$, $P_2$, and $P_5$, so $(1, 2, 5)$ is a good triplet. The other five good triplets are $(2, 3, 6)$, $(2, 4, 6)$, $(2, 5, 6)$, $(2, 5, 7)$, and $(2, 5, 8)$.