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

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