分数: 425 点
问题陈述
有一个池塘,周长为 M,在它的岸边矗立着一间小屋, N 人。
对于实数 x (0\leq x <M),定义点 x 作为位置 x 距小屋顺时针方向的距离。
的
树的 i- 第一个人已到达该点 A_i.
同一位置可能有多人站立。
另外,一个整数 C 不大于 给出了 N 。 对于 i=0,1,\ldots,M-1,定义 X_i 如下:
- 高桥从点开始 (i+0.5) 并开始顺时针移动。
- 高桥继续移动(顺时针),只要他遇到的总人数少于 C,并在变为时停止 C 或更多。在这里,“在某个时刻遇见一个人 y”表示高桥到达点 y.
- 让 X_i 是高桥在停车前遇到的人数。这里,如果高桥停下的地方有多个人,那么那里的所有人都算作他遇到的人,特别是, X_i 可能大于 C.
求总和 X_i 结束 i=0,1,\ldots,M-1,即 \displaystyle\sum_{i=0}^{M-1} X_i.
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M C A_1 A_2 \ldots A_N
输出
打印总和 X_i 结束 i=0,1,\ldots,M-1 在一行上。
示例输入 1
5 3 2 1 2 1 0 1
示例输出 1
9
当 i=0,高桥从点开始 0.5 并顺时针移动。然后,会发生以下情况:
- 在点 1,他遇到了 1圣, 3rd,和 5第人,一共三人,目前为止认识的总人数是 3。这不小于 C=2,所以高桥就停在那里。因此, X_0=3.
当 i=1,高桥从点开始 1.5 并顺时针移动。然后,会发生以下情况:
- 在点 2,他遇到了 2第一个人。目前为止已认识的总人数为 1,所以他继续移动。
- 在点 0,他遇到了 4第人,目前为止遇到的总人数是 2。这不小于 C=2,所以高桥就停在那里。因此, X_1=2.
当 i=2,高桥从点开始 2.5 并顺时针移动。然后,会发生以下情况:
- 在点 0,他遇到了 4第三个人。目前为止已认识的总人数为 1,所以他继续移动。
- 在点 1,他遇到了 1圣, 3rd,和 5第人,一共三人,目前为止认识的总人数是 4。这不小于 C=2,所以高桥就停在那里。因此, X_2=4.
因此,答案是 X_0+X_1+X_2=3+2+4=9.
示例输入 2
1 1000000000000 1 1
示例输出 2
1000000000000
无论起始位置如何,高桥在遇到唯一一个站在池塘周围的人时都会停下来。 1.
因此, X_i=1 无论 i,答案是 10^{12}.