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

Ran Yakumo симпатичная девочка, которая любит решать милые математические задачи.

Пусть $$$f(x)$$$ будет минимальным квадратом строго большим, чем $$$x$$$, и $$$g(x)$$$ будет максимальным квадратом, не строго меньшим, чем $$$x$$$. Например, $$$f(1)=f(2)=g(4)=g(8)=4$$$.

Натуральное целое число $$$x$$$ называется милым, если $$$x-g(x)<f(x)-x$$$. Например, $$$1,5,11$$$ это милые целые числа, а $$$3,8,15$$$ нет.

Ran Yakumo дает вам массив $$$a$$$ длины $$$n$$$. Она хочет, чтобы вы нашли минимальное неотрицательное целое число $$$k$$$, такое что $$$a_i + k$$$ является милым числом для любого элемента массива $$$a$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — длина $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 2\cdot 10^6$$$) — массив $$$a$$$.

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

Выведите одно целое число $$$k$$$ — ответ на задачу.

Примеры
Входные данные
4
1 3 8 10
Выходные данные
1
Входные данные
5
2 3 8 9 11
Выходные данные
8
Входные данные
8
1 2 3 4 5 6 7 8
Выходные данные
48
Примечание

В первом тесте $$$3$$$ не является красивым целым числом, поэтому $$$k\ne 0$$$.

$$$2,4,9,11$$$ являются милыми целыми числами, поэтому $$$k=1$$$.