28568번 - Ритуал очищения 다국어

Как известно, призраки и прочая нежить --- довольно несчастные существа. Каждый из них был бы, скорее всего, рад покинуть этот мир и отправиться в загробную жизнь, но большинство из них привязаны к этому миру проклятиями или контрактами. К счастью, у любого проклятия есть срок действия.

Каждый тринадцатый Хэллоуин всем проклятым позволено собраться вместе для очищения. Это ритуал, в котором все проклятые в произвольном порядке подходят к чаше с $x$ песчинками времени, и происходит следующее:

1. Количество песчинок в чаше возводится в квадрат, то есть становится равным $x^2$;
2. Время контракта или проклятия подошедшего существа $a_i$ уменьшается на $\min(a_i, x^2)$;
3. За каждую снятую единицу времени проклятия или контракта тратится одна песчинка. Таким образом, в чаше
4. остается $\max(0, x^2 - a_i)$ песчинок.

Например, если в чаше сейчас $3$ песчинки, то после того как подойдет существо с оставшимся временем действия проклятия $a_1 = 5$, все проклятие обнулится, после чего в чаше останется $3^2 - 5 = 4$ песчинки. Если после этого подойдет существо с $a_2 = 18$, чаша опустеет, а существо останется проклятым еще на $18 - 4^2 = 2$ года.

Уже через неделю состоится очередное очищение, и так сложилось, что вы можете немного повлиять на то, сколько в чаше будет песчинок в самом начале. Помогите призракам и всей остальной нечисти наконец-то обрести покой, и определите, какое минимальное количество песчинок должно быть в чаше, чтобы все существа могли избавиться от своих проклятий, подойдя к ней в каком-либо порядке.

В первой строке ввода дано единственное целое число $n$ ($1 \leq n \leq 10^5$) --- количество проклятых, которые собираются прийти на ближайшее очищение.

Во второй строке через пробел даны $n$ целых чисел $a_i$ ($1 \leq a_i \leq 10^{18}$) --- сроки проклятий и контрактов каждого из существ. Обратите внимание на то, что существа могут подходить к чаше в любом порядке, не обязательно в том, в котором они перечислены.

Выведите единственное целое число --- минимальное начальное количество песчинок в чаше, достаточное для полного очищения всех существ.