八云兰是一个可爱的女孩,喜欢创造可爱的数学问题。
设 $$$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$$$。