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$.

Input

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$.

Output

Print a single interger $k$ — the answer.

Note

Test case 1:

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

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