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^{\prime },b^{\prime },c^{\prime })$ are distinct if $a\ne a^{\prime }$, $b\ne b^{\prime }$, or $c\ne c^{\prime }$.

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.

Marks Awarded	Number of Points	Circumference	Additional Constraints
$3$ marks	$3\le N\le 200$	$3\le C\le {10}^6$	None
$3$ marks	$3\le N\le {10}^6$	$3\le C\le 6000$	None
$6$ marks	$3\le N\le {10}^6$	$3\le C\le {10}^6$	$P_1,P_2,\dots ,P_N$ are all distinct (i.e., every location contains at most one point)
$3$ marks	$3\le N\le {10}^6$	$3\le C\le {10}^6$	None

Output Specification

Output the number of distinct good triplets.

Sample Input

8 10
0 2 5 5 6 9 0 0

Output for Sample Input

6

Explanation of Output for Sample Input

Andrew drew the following diagram.

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)$.