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.

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