Cute number

题意翻译

> 蓝智力相当高，尤其擅长数学。据说连人类所无法想象程度的计算都能够在瞬间完成。——《东方求闻史纪》 [八云蓝](https://www.luogu.com.cn/user/149196)是一个很喜欢出可爱的数学题的可爱的女孩子。 定义 $f(x)$ 表示严格大于 $x$ 的最小的完全平方数，定义 $g(x)$ 为小于等于 $x$ 的最大的完全平方数。例如，$f(1)=f(2)=g(4)=g(8)=4$。 蓝认为，一个正整数是“可爱”的，当且仅当 $x-g(x)<f(x)-x$，例如，$1,5,11$ 是可爱的正整数，而 $3,8,15$ 不是。 蓝给了你一个长度为 $n$ 的正整数数列 $a_i$，你需要帮她找到最小的非负整数 $k$，使得对于 $\forall i$，$a_i+k$ 是可爱的。 **输入格式** 第一行输入一个正整数 $n(1 \leq n \leq 10^6)$，表示正整数数列的长度。 第二行输入 $n$ 个正整数 $a_i(1 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 2 \times 10^6)$。 **输出格式** 输出符合题目要求的最小非负整数 $k$。

题目描述

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](https://en.wikipedia.org/wiki/Square_number) strictly greater than $ x $ , and $ g(x) $ be the maximal square number not strictly less than $ x $ . For example, $ f(1)=f(2)=g(4)=g(8)=4 $ . "not strictly less than" means less than or equal to. 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.

输入输出样例

输入样例 #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

说明

Test case 1: $ 3 $ is not cute integer, so $ k\ne 0 $ . $ 2,4,9,11 $ are cute integers, so $ k=1 $ .

题目大意：
定义一个正整数为“可爱”，当且仅当它距离小于它的最大完全平方数的距离小于它距离大于它的最小完全平方数的距离。给定一个正整数数列，要找到一个非负整数k，使得每个数加上k后都是“可爱”的。

输入数据格式：
第一行输入一个正整数n（1≤n≤10^6），表示数列的长度。
第二行输入n个正整数a_i（1≤a_1≤a_2≤…≤a_n≤2×10^6），表示数列中的每个数。

输出数据格式：
输出符合题目要求的最小非负整数k。

例如：
输入样例：
4
1 3 8 10

输出样例：
1

解释：
当k=0时，3不是“可爱”的数。
当k=1时，2、4、9、11都是“可爱”的数，所以k=1。题目大意： 定义一个正整数为“可爱”，当且仅当它距离小于它的最大完全平方数的距离小于它距离大于它的最小完全平方数的距离。给定一个正整数数列，要找到一个非负整数k，使得每个数加上k后都是“可爱”的。 输入数据格式： 第一行输入一个正整数n（1≤n≤10^6），表示数列的长度。 第二行输入n个正整数a_i（1≤a_1≤a_2≤…≤a_n≤2×10^6），表示数列中的每个数。 输出数据格式： 输出符合题目要求的最小非负整数k。 例如： 输入样例： 4 1 3 8 10 输出样例： 1 解释： 当k=0时，3不是“可爱”的数。 当k=1时，2、4、9、11都是“可爱”的数，所以k=1。