← 返回题目列表

Codeforces · 429/D

D. 棘手的功能

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

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