本题的前 5 个子任务为场上原始的数据范围，我们添加了 4 个额外子任务，总分 105 分。

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

在一个周长为 $C$ 的圆形上分布有 $N$ 个点，问有多少种选择 $3$ 个点的方案使得圆心在以这三个点为顶点的三角形的内部（在三角形的边上是不合法的方案）。

圆上有 $C$ 个等距分布的位置，所有的 $N$ 个点只有可能分布在这 $C$ 个位置上。将这些位置顺时针编号为 $0$ 到 $C - 1$，第 $i$ 个点所处的位置是 $a_i$。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $N, C$。

输入的第二行包含 $N$ 个非负整数 $a_i$。

输出格式

输出到标准输出。

输出一个非负整数，表示对应的答案。

6 10
0 2 5 4 8 9

4

样例 1 解释

该样例一共有 $4$ 种选择的方案。

8 10
0 2 5 5 6 9 0 0

6

样例 2 解释

注意到有些点在圆上的同一位置，但是他们的编号不同，选择方案也会因此独立计算，故一共有 $6$ 种选择的方案。

子任务

对于原始的 5 组子任务，保证 $1 \le N \le 10^5,~1 \le C \le 10^5$。

对于额外子任务，保证 $1 \le N \le 10^6,~1 \le C \le 10^6$。

对于所有数据，保证 $0 \le a_i \lt C$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

特殊性质：保证不存在两个点位于圆上同一位置。