Яхаб, Сорин хоёр бол хот дахь хамгийн өрсөлдөх чадвартай программистууд юм. Хэдий тийм ч тэд хоёулаа маш чухал тэмцээний шаардлагыг хангаж чадсангүй. Сонголтыг нэг асуудлын тусламжтайгаар хийж болно. Яхабын найз Blatnatalag тэмцээний өмнө асуудлыг зохицуулж байгаа. Учир нь тэр Яхабыг чадварлаг нэгэн гэдэгт итгэдэг учраас Яхабд дараах үүргийг өгсөн.

Чамд $n$ элементтэй $a$ массив (нэг суурьтай) өгөгдсөн. $f(i, j)$ $(1 ≤ i, j ≤ n)$ функцыг $(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 ≠ j}  f(i, j)$-ийн утгийг ол.

Магадгүй одоо Яхаб аль хэдийн энэ асуудлын шийдлийг олж мэдсэн. Чи чадах уу?

Оролт

Эхний мөрөнд нь нэг бүхэл тоо $n$ ($2 ≤ n ≤ 100000$) байна. Дараагийн $n$ мөр нь $a[1]$, $a[2]$, ..., $a[n]$ ($ - 10^{4} ≤ a[i] ≤ 10^{4}$) бүхэл тоонуудыг агуулна.

Гаралт

$min_{i ≠ j}  f(i, j)$-ийн утга болох нэг бүхэл тоо хэвлэнэ.