A4651 | $爱干净的公主去上学$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

时间限制：1S 空间限制：256MB 今天安阳下了三十年来最大的暴雨，而去往教学楼的路被雨水淹没了，我们把从宿舍到教学楼的路径看成一条直线，宿舍在 $1$ 的位置，教学楼在 $n$ 的位置（宿舍和教学楼为落脚点），学校在这条直线上放置了 $m$ 个小型落脚平台，对于第 $i$ 个落脚平台放在了 $a_i$ 的位置，咱们的算法一姐超楠要顶着黑眼圈从宿舍去上早八，而她身为淑女肯定不愿意踩到水中，超楠一次可以从一个位置向前跳跃 $1 \sim k$ 之间的任意距离，超楠希望她能用最少跳的次数到教学楼，你能告诉她最少需要跳跃多少次吗，如果无论如何都跳不到教学楼输出-1。

第一行给出三个整数 $n,m,k$ ；第二行给出 $m$ 个数代表 $a_i$ ；对于所有数据 $1 \le m < n \le 5 \times 10^5；1 \le k \le 5 \times 10^5，1 \le a_i < n$。

输出一个整数为她最少跳跃的次数.

输入 #1

10 4 3
3 5 7 9

输出 #1

C++ 编辑器

输入

输出