AT_abc429_d.[ABC429D] On AtCoder Conference

有一个周长为 $M$ 的池塘，岸上有一座小屋和 $N$ 个人。
对于一个实数 $x$ （$0\leq x <M$），定义位置 $x$ 表示距离小屋顺时针方向 $x$ 的点。
第 $i$ 个人位于点 $A_i$。可能有多个人站在同一个位置。

另外，给定一个不超过 $N$ 的整数 $C$。对于 $i=0,1,\ldots,M-1$，定义 $X_i$ 如下：

1. 高桥从点 $(i+0.5)$ 出发，开始顺时针移动。
2. 只要他遇到的人数总和还不到 $C$，他就继续顺时针走，直到人数达到 $C$ 或更多时停止。在这里，“在点 $y$ 遇到某人”是指高桥到达点 $y$。
3. 令 $X_i$ 表示高桥在停下来前遇到的总人数。如果他在停下来的点有多个人，这些人全部计入遇到的人数，因此 $X_i$ 也有可能大于 $C$。

求 $X_i$ 对于 $i=0,1,\ldots,M-1$ 的和，即 $\displaystyle\sum_{i=0}^{M-1} X_i$。

输入按下述格式给出：

$N$ $M$ $C$
$A_1$ $A_2$ $\ldots$ $A_N$

输出一行，表示 $X_i$ 的和，即 $\displaystyle\sum_{i=0}^{M-1} X_i$。

样例解释 1

当 $i=0$ 时，高桥从 $0.5$ 出发，顺时针走一圈，过程如下：

• 到达 $1$，遇到第 $1$、第 $3$ 和第 $5$ 个人，总共 $3$ 人，此时达到了 $C=2$，高桥在此处停下。因此 $X_0=3$。

当 $i=1$ 时，高桥从 $1.5$ 出发，顺时针走一圈，过程如下：

• 到达 $2$，遇到第 $2$ 个人，总人数 $1$，还没达到 $C$。
• 到达 $0$，遇到第 $4$ 个人，总数达到 $2$，达到 $C$，高桥停止。因此 $X_1=2$。

当 $i=2$ 时，高桥从 $2.5$ 出发，顺时针走一圈，过程如下：

• 到达 $0$，遇到第 $4$ 个人，总数 $1$，继续前进。
• 到达 $1$，遇到第 $1$、第 $3$ 和第 $5$ 个人，总共 $3$ 人，加上之前的 $1$ 人，总数 $4$，达到 $C$，高桥停止。因此 $X_2=4$。

因此答案为 $X_0+X_1+X_2=3+2+4=9$。

样例解释 2

无论从哪里出发，高桥都会在遇到唯一的那个人（他站在 $1$ 位置）时停下。
因此，对任意 $i$ 有 $X_i=1$，答案为 $10^{12}$。

数据范围

• $1\leq N\leq 5\times 10^5$
• $1\leq M\leq 10^{12}$
• $0\leq A_i\leq M-1$
• $1\leq C\leq N$
• 输入的所有数均为整数。

由 ChatGPT 5 翻译