F. Порталы
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На прямой расположено $$$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$$$ энергии. Можно показать, что при вышеописанных ограничениях на входные данные это всегда возможно.

Примеры
Входные данные
2
1 5
7
Выходные данные
2
Входные данные
2
1 5
6
Выходные данные
3
Входные данные
1
5
5
Выходные данные
4
Входные данные
1
1000000000
1000000043
Выходные данные
999999978