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*)<sup class="upper-index">2</sup> + *g*(*i*, *j*)<sup class="upper-index">2</sup>. Function g is calculated by the following pseudo-code:

Find a value *min*<sub class="lower-index">*i* ≠ *j*</sub>  *f*(*i*, *j*).

Probably by now Iahub already figured out the solution to this problem. Can you?
The first line of input contains a single integer *n* (2 ≤ *n* ≤ 100000). Next line contains *n* integers *a*[1], *a*[2], ..., *a*[*n*] ( - 10<sup class="upper-index">4</sup> ≤ *a*[*i*] ≤ 10<sup class="upper-index">4</sup>).
import bisect
import heapq
import sys
from types import GeneratorType
from functools import cmp_to_key
from collections import defaultdict, Counter, deque
import math
from functools import lru_cache
from heapq import nlargest
from functools import reduce
import random
from itertools import combinations
from itertools import accumulate
from operator import xor, add
from operator import mul
from typing import List
random.seed(2023)
inf = float("inf")
PLATFORM = "CF"
if PLATFORM == "LUOGU":
    import numpy as np

    sys.setrecursionlimit(1000000)


class FastIO:
    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return float(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(" ".join(str(w) for w in x) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, queue=[]):
        def wrappedfunc(*args, **kwargs):
            if queue:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        queue.append(to)
                        to = next(to)
                    else:
                        queue.pop()
                        if not queue:
                            break
                        to = queue[-1].send(to)
                return to

        return wrappedfunc

    def ask(self, lst):
        self.lst(lst)
        sys.stdout.flush()
        res = self.read_int()
        return res


class ClosetPair:
    def __init__(self):
        return

    @staticmethod
    def bucket_grid(n: int, nums: List[List[int]]):

        # 模板：使用随机增量法分网格计算平面最近的点对
        def dis(p1, p2):
            return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])

        def check(p):
            return p[0] // ss, p[1] // ss

        def update(buck, ind):
            if buck not in dct:
                dct[buck] = []
            dct[buck].append(ind)
            return

        assert n >= 2
        random.shuffle(nums)

        # 初始化
        dct = dict()
        update(check(nums[0]), 0)
        update(check(nums[1]), 1)
        ans = dis(nums[0], nums[1])
        ss = ans**0.5
        if ans == 0:
            return 0

        # 遍历进行随机增量
        for i in range(2, n):
            a, b = check(nums[i])
            res = ans
            for x in [-1, 0, 1]:
                for y in [-1, 0, 1]:
                    cur = (x+a, y+b)
                    if cur in dct:
                        for j in dct[cur]:
                            now = dis(nums[i], nums[j])
                            res = res if res < now else now
            if res == 0:  # 距离为 0 直接返回
                return 0
            if res < ans:
                # 重置初始化
                ans = res
                ss = ans**0.5
                dct = dict()
                for x in range(i+1):
                    update(check(nums[x]), x)
            else:
                update(check(nums[i]), i)
        # 返回值为欧几里得距离的平方
        return ans

    @staticmethod
    def divide_and_conquer(lst):

        # 模板：使用分治求解平面最近点对
        lst.sort(key=lambda p: p[0])

        def distance(p1, p2):
            return (p1[0] - p1[0]) * (p2[0] - p2[0]) + (p1[1] - p1[1]) * (p2[1] - p2[1])

        def conquer(point_set, min_dis, mid):
            smallest = min_dis
            point_mid = point_set[mid]
            pt = []
            for point in point_set:
                if (point[0] - point_mid[0]) ** 2 <= min_dis:
                    pt.append(point)
            pt.sort(key=lambda x: x[1])
            for i in range(len(pt)):
                for j in range(i + 1, len(pt)):
                    if (pt[i].y - pt[j].y) ** 2 >= min_dis:
                        break
                    cur = distance(pt[i], pt[j])
                    smallest = smallest if smallest < cur else cur
            return smallest

        def check(point_set):
            min_dis = float("inf")
            if len(point_set) <= 3:
                n = len(point_set)
                for i in range(n):
                    for j in range(i + 1, n):
                        cur = distance(point_set[i], point_set[j])
                        min_dis = min_dis if min_dis < cur else cur
                return min_dis
            mid = len(point_set) // 2
            left = point_set[:mid]
            right = point_set[mid + 1:]
            min_left_dis = check(left)
            min_right_dis = check(right)
            min_dis = min_left_dis if min_left_dis < min_right_dis else min_right_dis
            merge_dis = conquer(point_set, min_dis, mid)
            return min_dis if min_dis < merge_dis else merge_dis
    
        return check(lst)


class Solution:
    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        n = ac.read_int()
        nums = ac.read_list_ints()
        n = int(n)
        nums = list(accumulate(nums, add))
        nums = [[i, nums[i]] for i in range(n)]
        ans = ClosetPair().bucket_grid(n, nums)
        ac.st(ans)
        return


Solution().main()