E. Квадраты и не квадраты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ани и Бори есть n кучек с конфетами, причём n чётное число: i-я кучка содержит ai конфет.

Аня любит числа, которые являются квадратами целых чисел, а Боря любит числа, которые не являются квадратами целых чисел. За один ход ребята совместно договариваются выбрать какую-то кучку с конфетами и положить в неё одну новую конфету (которая до этого не лежала ни в одной кучке), либо взять из этой кучки конфету (если эта кучка не пуста), и съесть её.

Определите минимальное количество ходов, необходимых для того, чтобы ровно n / 2 кучек содержали количества конфет, являющиеся квадратами целых чисел, а оставшиеся n / 2 кучек содержали количества конфет, не являющиеся квадратами целых чисел.

Входные данные

В первой строке следует целое чётное число n (2 ≤ n ≤ 200 000) — количество кучек с конфетами.

Во второй строке следует последовательность a1, a2, ..., an (0 ≤ ai ≤ 109) — размеры кучек с конфетами.

Выходные данные

Выведите минимальное количество ходов, необходимых для того, чтобы ровно n / 2 кучек содержали количества конфет, являющиеся квадратами целых чисел, а другие n / 2 кучек содержали количества конфет, не являющиеся квадратами целых чисел. Если для выполнения этих условий не нужно делать ни одного хода, выведите 0.

Примеры
Входные данные
4
12 14 30 4
Выходные данные
2
Входные данные
6
0 0 0 0 0 0
Выходные данные
6
Входные данные
6
120 110 23 34 25 45
Выходные данные
3
Входные данные
10
121 56 78 81 45 100 1 0 54 78
Выходные данные
0
Примечание

В первом примере достаточно двух ходов. На каждом ходу нужно класть новую конфету во вторую кучку. После этого её размер станет равным 16, поэтому у Ани и Бори станет две кучки, чьи размеры являются квадратами целых чисел (вторая и четвертая кучки), и две кучки, чьи размеры не являются квадратами целых чисел (первая и третья кучки).

Во втором примере необходимо добавить по две конфеты в любые три кучки.