F. Teleporterstime limit per test7 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThere are n+1 teleporters on a straight line, located in points 0, a_1, a_2, a_3, ..., a_n. It's possible to teleport from point x to point y if there are teleporters in both of those points, and it costs (x-y)^2 energy.You want to install some additional teleporters so that it is possible to get from the point 0 to the point a_n (possibly through some other teleporters) spending no more than m energy in total. Each teleporter you install must be located in an integer point.What is the minimum number of teleporters you have to install?InputThe first line contains one integer n (1 \le n \le 2 \cdot 10^5).The second line contains n integers a_1, a_2, \dots, a_n (1 \le a_1 < a_2 < a_3 < \dots < a_n \le 10^9).The third line contains one integer m (a_n \le m \le 10^{18}).OutputPrint one integer — the minimum number of teleporters you have to install so that it is possible to get from 0 to a_n spending at most m energy. It can be shown that it's always possible under the constraints from the input format.ExamplesInput
2
1 5
7
Output
2
Input
2
1 5
6
Output
3
Input
1
5
5
Output
4
Input
1
1000000000
1000000043
Output
999999978

2
1 5
7

2 
['binary search', 'greedy', '*2600']