直线上有 $$$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