← 返回题目列表

Codeforces · 1687/D

D. 可爱的数字

中文机器翻译题面 查看原题

八云兰是一个可爱的女孩,喜欢创造可爱的数学问题。

设 $$$f(x)$$$ 为严格大于 $$$x$$$ 的最小平方数,$$$g(x)$$$ 为小于或等于 $$$x$$$ 的最大平方数。例如,$$$f(1)=f(2)=g(4)=g(8)=4$$$。

如果 $$$x-g(x)<f(x)-x$$$ 则正整数 $$$x$$$ 很可爱。例如,$$$1,5,11$$$ 是可爱的整数,而 $$$3,8,15$$$ 则不是。

Ran 给你一个长度为 $$$n$$$ 的数组 $$$a$$$。她希望你找到最小的非负整数 $$$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$$$ — 答案。

示例

输入 #1

4
1 3 8 10

输出 #1

1

输入 #2

5
2 3 8 9 11

输出 #2

8

输入 #3

8
1 2 3 4 5 6 7 8

输出 #3

48

注意

测试用例1:

$$$3$$$ 不是可爱的整数,所以 $$$k\ne 0$$$。

$$$2,4,9,11$$$ 是可爱的整数,所以 $$$k=1$$$。