Description

我们将任意两个相邻数相加均为完全平方数的数组称为完全平方数组，即如果长度为 $N$ 的数组 $A$ 为完全平方数组，则 $\forall i \in [1,N) , A[i]+A[i+1]$为完全平方数（完全平方数是指一个正整数，如果它可以表示为某个整数的平方，则称该正整数为完全平方数）

给你一个长度为 $n$ 的数组 $a$,以及如下三种操作：

• 将数组中任意一个数字 $a[i]$ 修改为 $a[i]+1$ 或 $a[i]-1$,代价为 $1$
• 将数组所有数字修改为任意正整数 $x$, 代价为 $x^2$
• 对数组求前缀和操作，即对于$1 \leq i \leq n$，$a[i] 变为 \sum_1^i a[i]$,代价为 $0$

请问将该数组修改为完全平方数组的最小代价是多少？

Format

Input

每个测试点只有一组测试数据

第一行一个正整数 $n(2 \leq n \leq 1e5)$，代表数组大小
第二行 $n$ 个整数 $a_i(0 \leq a_i \leq 5e5)$，代表数组第 $i$ 个元素

Output

输出将给定数组修改为完全平方数组的最小代价

Samples

5
1 2 7 18 7

1