ccpc大学生程序设计竞赛题目

以下是CCPC大学生程序设计竞赛的一道题目示例：

题目描述

有 $n$ 个人，他们各自有一个排名 $a_i$（$1 \le i \le n$），表示在比赛中他们的名次。现在他们要排成一列，满足两个条件：

- 相邻两个人的排名差不超过 $k$。
- 整个队伍的排名差最大。

请你计算最大的排名差。

输入格式

第一行包含三个整数 $n,m,k$，表示人数，排名最大值，以及相邻两个人排名差的最大值。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个人的排名。

输出格式

输出一个整数，表示最大的排名差。

数据范围

$1 \le n \le 2 \times 10^5$

$1 \le m \le 10^9$

$0 \le k \le m$

$1 \le a_i \le m$

样例

输入样例1：

5 20 3
1 5 10 15 20

输出样例1：

5

输入样例2：

5 20 4
1 5 10 15 20

输出样例2：

4

提示

样例1中的最优方案为 $1,5,10,15,20$，排名差为 $5$。

样例2中的最优方案为 $1,5,10,15,20$ 和 $5,10,15,20,1$，排名差均为 $4$。