| Codeforces Round 796 (Div. 1) |
|---|
| Finished |
Ran Yakumo is a cute girl who loves creating cute Maths problems.
Let $$$f(x)$$$ be the minimalsquare numberstrictly 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$$$ iscute 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.
41 3 8 10
1
52 3 8 9 11
8
81 2 3 4 5 6 7 8
48
Test case 1:
$$$3$$$ is not cute integer, so $$$k\ne 0$$$.
$$$2,4,9,11$$$ are cute integers, so $$$k=1$$$.
| Name |
|---|