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 \geq 3~ points at integer locations. In particular, the ~i^\text{th}~ point is drawn at location ~P_i~ (~0 \leq P_i \leq 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 \leq a < b < c \leq 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 \neq a'~, ~b \neq b'~, or ~c \neq 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.

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 6\,000~	None
~6~ marks	~3 \le N \le 10^6~	~3 \le C \le 10^6~	~P_1,P_2,...,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)~.