构造矩形
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}现有 n 条长度为 m 的线段,垂直于 x 轴分布,且互不重合。第 i 条线段的两个端点均为整数点,分别为 (a_i, 0) 和 (a_i, m)。每条线段上有 m+1 个整数点,纵坐标分别为 0,1,2,\dots, m
\hspace{15pt}现在,你需要选择两条不同的线段,并在每一条线段上各选择两个不同的整数点,要求这四个点连接构成的四边形恰好是一个矩形,且矩形的长减去宽为 k。请问一共有多少种选择方案?

输入描述:

\hspace{15pt}第一行输入三个整数 n,m,k \left(1\le n,m \le 10^5;\ 1 \le k < m\right) 代表线段条数、线段的长度、要求构成的矩形长宽之差。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(1\le a_1 \lt a_2 \lt \dots \lt a_n \le 10^5\right) 代表第 i 条线段端点的横坐标。

输出描述:

\hspace{15pt}输出一个整数,代表一共有多少种选择方案。我们可以证明,答案不会超过 10^{18}
示例1

输入

复制
3 2 1
1 2 3

输出

复制
4

说明

\hspace{15pt}在这个样例中,四种不同的选择方案如下图所示:


示例2

输入

复制
6 9 4
1 2 3 4 5 8

输出

复制
70