На прямой расположено $$$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
