CF429D.Tricky Function

Iahub and Sorin are the best competitive programmers in their town. However, they can't both qualify to an important contest. The selection will be made with the help of a single problem. Blatnatalag, a friend of Iahub, managed to get hold of the problem before the contest. Because he wants to make sure Iahub will be the one qualified, he tells Iahub the following task.

You're given an (1-based) array a with n elements. Let's define function f(i, j) (1 ≤ i, j ≤ n) as (i - j)2 + g(i, j)2. Function g is calculated by the following pseudo-code:

int g(int i, int j) {
int sum = 0;
for (int k = min(i, j) + 1; k <= max(i, j); k = k + 1)
sum = sum + a[k];
return sum;
}

Find a value min__i ≠ j f(i, j).

Probably by now Iahub already figured out the solution to this problem. Can you?

伊阿胡布和索林是他们小镇上最优秀的两名竞技程序员。然而，他们两人无法同时获得一场重要比赛的参赛资格。最终的选拔将通过一道题目来决定。布拉特纳塔拉格是伊阿胡布的一位朋友，他在比赛前设法获取了这道题目。由于他希望确保伊阿胡布能够获得资格，于是向伊阿胡布提出了如下任务：

给定一个长度为 $ n $ 的（下标从 1 开始的）数组 $ a $。定义函数 $ f(i, j) $（其中 $ 1 \le i, j \le n $）为

$$f(i, j) = (i - j)^2 + g(i, j)^2.$$

函数 $ g $ 由以下伪代码计算：

int g(int i, int j) {  
    int sum = 0;  
    for (int k = min(i, j) + 1; k <= max(i, j); k = k + 1)  
        sum = sum + a[k];  
    return sum;  
}

请找出 $ \min_{i \neq j} f(i, j) $ 的值。

此时，伊阿胡布很可能已经想出了这道题的解法。你能吗？

The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 104 ≤ a[i] ≤ 104).

输入的第一行包含一个整数 $n$（$2 \leq n \leq 100000$）。第二行包含 $n$ 个整数 $a[1],\ a[2],\ \dots,\ a[n]$（$-10^4 \leq a[i] \leq 10^4$）。

Output a single integer — the value of min__i ≠ j f(i, j).

输出一个整数——即 $\min_{i \neq j} f(i, j)$ 的值。