На прямой расположено \(n+1\) порталов. Они находятся в точках \(0\), \(a_1\), \(a_2\), \(a_3\), ..., \(a_n\). Можно телепортироваться из точки \(x\) в точку \(y\), если в обеих этих точках есть порталы, и такая телепортация стоит \((x-y)^2\) энергии.
Вы хотите установить несколько дополнительных порталов так, чтобы можно было телепортироваться из точки \(0\) в точку \(a_n\) (возможно, через какие-то промежуточные порталы), потратив суммарно не более \(m\) энергии. Каждый портал, который вы устанавливаете, должен располагаться в целочисленной точке.
Какое минимальное количество порталов вам нужно установить?
Выходные данные
Выведите одно целое число — минимальное количество порталов, которое нужно установить, чтобы можно было телепортироваться из точки \(0\) в точку \(a_n\), потратив суммарно не более \(m\) энергии. Можно показать, что при вышеописанных ограничениях на входные данные это всегда возможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 5
7
|
2
|
|
2
|
2
1 5
6
|
3
|
|
3
|
1
5
5
|
4
|
|
4
|
1
1000000000
1000000043
|
999999978
|