[AdditionalFile5617.zip](file://AdditionalFile5617.zip?type=additional_file)

#5617. 「PA 2016 Final」Waga

标签: 传统 | 时间限制: 3000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2016 Final Waga

Bajtazar 在十三岁生日那天收到了一台秤作为礼物。他非常喜欢这份礼物，立即开始称量身边的所有物品。然而，很快他就发现这台秤并不太精准：它显示的质量总是向下取整到最接近的 $c$ 克的倍数。此外，这台秤还有一个缺陷：若放在上面的载荷质量达到或超过 $k \cdot c$ 克，秤就会报错，不显示任何数值。

起初，Bajtazar 感到很沮丧，觉得无法精确称量出所有物品的质量。尽管如此，他还是想利用「一次可以将多个物品放在秤上」这一事实，尽可能多地了解这些物品的信息。通过这种方式，他可以获得关于物品质量的额外信息。例如，这可能足以让他在面对某些物品对时，确信其中一个比另一个重。

你的任务是确定有多少对物品 $(x, y)$，使得 Bajtazar 能够利用这台秤推断出 $x$ 的质量比 $y$ 大。幸运的是，Bajtazar 拥有的所有物品的质量都是 $1$ 克的整数倍。然而，我们假设 Bajtazar 本人并不知道这些具体质量。此外，他也并不知道物品质量是整数；他仅假设每个质量都是某个正实数。不过，Bajtazar 知道 $k$ 和 $c$ 的值：他已经在说明书中找到了它们。

输入格式

第一行包含三个整数 $n, k$ 和 $c$ $(1 \leq n, k \leq 1000, 1 \leq c \leq 5000)$，分别表示 Bajtazar 拥有的物品数量以及秤的参数。这台秤的称重精度为 $c$ 克，并显示向下取整后的质量（如果载荷质量小于 $k \cdot c$ 克）；如果载荷质量达到或超过 $k \cdot c$ 克，秤则会发出错误信号。

第二行包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$ $(1 \leq a_{i} < k \cdot c)$，表示各个物品的实际质量（单位：克）。

输出格式

输出一个整数，表示有多少对物品 $(x, y)$，满足经过若干次称量后可以推断出 $x$ 的质量大于 $y$。

样例

输入

4 4 6
8 9 10 11

输出

4

Bajtazar 能够推断出，在物品对 $(1,3), (1,4), (2,3)$ 和 $(2,4)$ 中，两者的质量是不同的。