← 返回题目列表

Codeforces · 1661/F

F. 传送器

中文机器翻译题面 查看原题

直线上有 $$$n+1$$$ 传送器,位于 $$$0$$$、$$$a_1$$$、$$$a_2$$$、$$$a_3$$$、...、$$$a_n$$$ 点。如果 $$$x$$$ 点和 $$$y$$$ 点都有传送器,则可以从这两个点传送到这两个点,并且需要花费 $$$(x-y)^2$$$ 能量。

您想要安装一些额外的传送器,以便可以从 $$$0$$$ 点到达 $$$a_n$$$ 点(可能通过一些其他传送器)总共花费不超过 $$$m$$$ 能量。您安装的每个传送器必须位于一个整数点。

您必须安装的传送器最少数量是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 < a_2 < a_3 < \dots < a_n \le 10^9$$$)。

第三行包含一个整数$$$m$$$ ($$$a_n \le m \le 10^{18}$$$)。

输出

打印一个整数 — 您必须安装的传送器的最小数量,以便可以从 $$$0$$$ 到 $$$a_n$$$ 花费最多 $$$m$$$ 能量。可以证明,在输入格式的约束下,它总是可能的。

示例

输入 #1

2
1 5
7

输出 #1

2

输入 #2

2
1 5
6

输出 #2

3

输入 #3

1
5
5

输出 #3

4

输入#4

1
1000000000
1000000043

输出#4

999999978