有 $$$n$$$ 名学生,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 学生的级别为 $$$a_i$$$。您需要将学生分成稳定的小组。如果一组学生在其级别的排序数组中没有两个相邻元素相差超过 $$$x$$$,则称该组学生是稳定的。
例如,如果 $$$x = 4$$$,则级别为 $$$[1, 10, 8, 4, 4]$$$ 的组是稳定的(因为 $$$4 - 1 \le x$$$、$$$4 - 4 \le x$$$、$$$8 - 4 \le x$$$、$$$10 - 8 \le x$$$),而级别为 $$$[2, 10, 10, 7]$$$ 的组不稳定 ($$$7 - 2 = 5 > x$$$)。
除了给定的 $$$n$$$ 学生外,教师最多可以邀请任意级别的 $$$k$$$ 额外学生(由教师选择)。求教师可以从所有学生(包括新邀请的学生)中形成稳定小组的最少数量。
例如,如果有两个级别为 $$$1$$$ 和 $$$5$$$ 的学生; $$$x = 2$$$;和 $$$k \ge 1$$$,那么你可以邀请一个级别为 $$$3$$$ 的新学生,并将所有学生放在一个稳定的组中。
输入
第一行包含三个整数 $$$n$$$, $$$k$$$, $$$x$$$ ($$$1 \le n \le 200\,000$$$, $$$0 \le k \le 10^{18}$$$, $$$1 \le x \le 10^{18}$$$) — 学生的初始人数,您可以额外邀请的学生,以及允许的最大级别差异。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — 学生级别。
输出
在唯一的一行中打印一个整数:您可以将学生分成的稳定组的最小数量。
示例
输入 #1
8 2 3 1 1 5 8 12 13 20 22
输出 #1
2
输入 #2
13 0 37 20 20 80 70 70 70 420 5 1 5 1 60 90
输出 #2
3
注意
在第一个示例中,您可以邀请级别为 $$$2$$$ 和 $$$11$$$ 的两名学生。然后你可以将学生分成两个稳定的组:
1. $$$[1, 1, 2, 5, 8, 11, 12, 13]$$$,
2. $$$[20, 22]$$$.
在第二个示例中,您不允许邀请新学生,因此您需要 $$$3$$$ 组:
1. $$$[1, 1, 5, 5, 20, 20]$$$
2. $$$[60, 70, 70, 70, 80, 90]$$$
3. $$$[420]$$$