codeforces#P1687D. Cute number

    ID: 32985 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbrute forceimplementationmath*2900

Cute number

Description

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

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

Print a single interger $k$ — the answer.

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.

Samples

4
1 3 8 10
1
5
2 3 8 9 11
8
8
1 2 3 4 5 6 7 8
48

Note

Test case 1:

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

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