CF1687D.Cute number

Ran is especially skilled in computation and mathematics. It is said that she can do unimaginable calculation work in an instant.

—Perfect Memento in Strict Sense

Ran Yakumo is a cute girl who loves creating cute Maths problems.

Let $f(x)$ be the minimal square number strictly greater than $x$, and $g(x)$ be the maximal square number less than or equal to $x$. For example, $f(1)=f(2)=g(4)=g(8)=4$.

A positive integer $x$ is cute if $x-g(x) \lt f(x)-x$. For example, $1,5,11$ are cute integers, while $3,8,15$ are not.

Ran gives you an array $a$ of length $n$. She wants you to find the smallest non-negative integer $k$ such that $a_i + k$ is a cute number for any element of $a$.

莲尤其擅长计算与数学。据说她能在瞬间完成难以想象的计算工作。

——《严格意义下的完美记忆》

八云莲是一位喜爱创造可爱数学题的可爱女孩。

令 $f(x)$ 表示严格大于 $x$ 的最小平方数，而 $g(x)$ 表示小于或等于 $x$ 的最大平方数。例如，$f(1)=f(2)=g(4)=g(8)=4$。

一个正整数 $x$ 被称为“可爱的”，当且仅当 $x-g(x) \lt f(x)-x$。例如，$1,5,11$ 是可爱的整数，而 $3,8,15$ 则不是。

莲给你一个长度为 $n$ 的数组 $a$。她希望你找出最小的非负整数 $k$，使得对数组 $a$ 中的每个元素 $a_i$，$a_i + k$ 都是可爱的数。

The first line contains one integer $n$ ($1 \leq n \leq 10^6$) — the length of $a$.

The second line contains $n$ intergers $a_1,a_2,\ldots,a_n$ ($1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 2\cdot 10^6$) — the array $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$。

Print a single interger $k$ — the answer.

输出一个整数 $k$ —— 答案。

Test case 1:

$3$ is not cute integer, so $k\ne 0$.

$2,4,9,11$ are cute integers, so $k=1$.

测试用例 1：

$3$ 不是可爱的整数，因此 $k\ne 0$。

$2,4,9,11$ 是可爱的整数，因此 $k=1$。