Teleporters

ID: 1263

Type: RemoteJudge

7000ms

512MiB

Tried: 0

Accepted: 0

Difficulty: 10

Uploaded By:

Hydro

Tags>

binary search

greedy

*2600

Description

There 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?

The 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}$ ).

Print 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.

Input

The 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}$ ).

Output

Sample Input 1

2
1 5
7

Sample Output 1

Sample Input 2

2
1 5
6

Sample Output 2

Sample Input 3

1
5
5

Sample Output 3

Sample Input 4

1
1000000000
1000000043

Sample Output 4

999999978

#P1661F. Teleporters

Description

Input

Output

Status

Development

Support

#P1661F. Teleporters

Teleporters

Description

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Status

Development

Support

Don't have an account?

SIGN IN