Iahub 和 Sorin 是他们镇上最有竞争力的程序员。然而,他们无法同时获得参加重要比赛的资格。将在单个问题的帮助下进行选择。 Iahub 的朋友 Blatnatalag 在比赛前设法解决了这个问题。因为他想确保 Iahub 是合格的人选,所以他告诉 Iahub 以下任务。
给定一个包含 n 个元素的(从 1 开始的)数组 a。我们将函数 f(i, j) (1 ≤ i, j ≤ n) 定义为 (i - j)2 + g(i, j)2。函数 g 由以下伪代码计算:
找到一个值 mini ≠ j f(i, j)。
可能现在 Iahub 已经找到了这个问题的解决方案。你可以吗?
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 100000)。下一行包含 n 个整数 a[1], a[2], ..., a[n] ( - 104 ≤ a[i] ≤ 104)。
输出
输出一个整数 — mini ≠ j f(i, j) 的值。
示例
输入 #1
4 1 0 0 -1
输出 #1
1
输入 #2
2 1 -1
输出 #2
2