D. Ярвигтай функц

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Яхаб, Сорин хоёр бол хот дахь хамгийн өрсөлдөх чадвартай программистууд юм. Хэдий тийм ч тэд хоёулаа маш чухал тэмцээний шаардлагыг хангаж чадсангүй. Сонголтыг нэг асуудлын тусламжтайгаар хийж болно. Яхабын найз 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)$-ийн утга болох нэг бүхэл тоо хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
4
1 0 0 -1
Гаралт
1
Оролт
2
1 -1
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...