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>).
from fractions import Fraction


class loose_float(float):

    EPS = 10 ** -10

    def __eq__(self, other):
        return abs(self - other) < self.__class__.EPS

    def __lt__(self, other):
        return self.__class__.EPS < other - self

    def __le__(self, other):
        return -self.__class__.EPS <= other - self

    def __gt__(self, other):
        return self.__class__.EPS < self - other

    def __ge__(self, other):
        return -self.__class__.EPS <= self - other


# T = Fraction
# T = float
# T = loose_float
T = int

INF = T(10 ** 18)


class Point:

    def __init__(self, x, y):
        self.x = T(x)
        self.y = T(y)

    def __neg__(self):
        return self.__class__(-self.x, -self.y)

    def __add__(self, other):
        return self.__class__(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return self.__class__(self.x - other.x, self.y - other.y)

    def __mul__(self, other):
        if isinstance(other, type(self)):
            return self.__class__(self.x * other.x - self.y * other.y, self.x * other.y + self.y * other.x)
        else:
            return self.__class__(self.x * other, self.y * other)

    __rmul__ = __mul__

    def norm_square(self):
        return self.x * self.x + self.y * self.y

    def inv(self):
        return self.__class__(self.x, -self.y) * (1 / self.norm_square())

    def __truediv__(self, other):
        if isinstance(other, type(self)):
            return self * other.inv()
        else:
            return self.__class__(self.x / other, self.y / other)

    def __eq__(self, other):
        return (self.x == other.x and self.y == other.y)

    def __lt__(self, other):
        return (self.x < other.x or (self.x == other.x and self.y < other.y))

    def __le__(self, other):
        return (self.x < other.x or (self.x == other.x and self.y <= other.y))

    def __repr__(self):
        return "%s(%s, %s)" % (self.__class__.__name__,
                               self.x, self.y)


Vec = Point


class Line:

    def __init__(self, a: Point, b: Point):
        self.a = a
        self.b = b

    def __eq__(self, other):
        return _intersect_line_line(self, other) == 2  # -1 に変えること。

    def __repr__(self):
        return "%s(%s, %s)" % (self.__class__.__name__,
                               self.a, self.b)


class Segment(Line):

    def __eq__(self, other):
        return (self.a == other.a and self.b == other.b) or ((self.a == other.b and self.b == other.a))


class Real_Circle:

    def __init__(self, center: Point, radius, radius_is_squared: bool = False):
        self.center = center
        radius = T(radius)
        if radius_is_squared:
            self.radius_square = radius
        else:
            self.radius_square = radius * radius

    def __eq__(self, other):
        return (self.center == other.center and self.radius_square == other.radius_square)

    def __repr__(self):
        return "%s(center=%s, r**2=%s)" % (self.__class__.__name__,
                                           self.center, self.radius_square)


class Rational_Circle(Real_Circle):

    def __init__(self, center: Point, radius, radius_is_squared: bool = False):
        self.radius = T(radius)
        super().__init__(center, radius, False)

    def __repr__(self):
        return "%s(center=%s, r=%s)" % (self.__class__.__name__,
                                        self.center, self.radius)


def dot(a: Vec, b: Vec) -> T:
    return a.x * b.x + a.y * b.y


def cross(a: Vec, b: Vec) -> T:
    return a.x * b.y - a.y * b.x


def parallel(a, b):
    if isinstance(a, Line) or isinstance(a, Segment):
        a = a.b - a.a
    if isinstance(b, Line) or isinstance(b, Segment):
        b = b.b - b.a
    return cross(a, b) == 0


def orthogonal(a, b):
    if isinstance(a, Line) or isinstance(a, Segment):
        a = a.b - a.a
    if isinstance(b, Line) or isinstance(b, Segment):
        b = b.b - b.a
    return dot(a, b) == 0


def ccw(a: Point, b: Point, c: Point):
    """
    0: c is on [a, b]
    1: counter clockwise
    -1: clockwise
    2: c a b
    -2: a b c
    https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_1_C/judge/5781413/Python3    """
    b -= a
    c -= a
    if cross(b, c) > 0:
        return +1  # "COUNTER_CLOCKWISE"
    if cross(b, c) < 0:
        return -1  # "CLOCKWISE"
    if dot(b, c) < 0:
        return +2  # "ONLINE_BACK" [c, a, b]
    if b.norm_square() < c.norm_square():
        return -2  # "ONLINE_FRONT" [a, b, c]
    return 0  # "ON_SEGMENT" c is on [a, b]


def projection(l, p: Point) -> Point:
    return l.a + (l.b - l.a) * (dot(p - l.a, l.b - l.a) / (l.b - l.a).norm_square())


def reflection(l, p: Point) -> Point:
    return projection(l, p) * 2 - p


def _intersect_line_point(l: Line, p: Point):
    return int(abs(ccw(l.a, l.b, p)) != 1)


def _intersect_segment_point(s: Segment, p: Point):
    return int(ccw(s.a, s.b, p) == 0)


def _intersect_line_line(l: Line, m: Line):
    if cross(l.a - l.b, m.a - m.b) != 0:
        return 1
    return 0 if abs(ccw(l.a, l.b, m.a)) == 1 else 2


def _intersect_line_segment(l: Line, s: Segment):
    a = ccw(l.a, l.b, s.a)
    b = ccw(l.a, l.b, s.b)
    if a * b == 1:
        return 0
    if a * b == -1 or (a + b) % 2:
        return 1
    return 2


def _distance_square_point_point(a: Point, b: Point) -> T:
    return (a - b).norm_square()


def _distance_square_line_point(l: Line, p: Point) -> T:
    return _distance_square_point_point(p, projection(l, p))


def _intersect_circle_line(c: Real_Circle, l: Line):
    d = _distance_square_line_point(l, c.center)
    if d > c.radius_square:
        return 0
    if d == c.radius_square:
        return 1
    return 2


def _intersect_circle_point(c: Real_Circle, p: Point):
    return int((p - c.center).norm_square() == c.radius_square)


def _intersect_segment_segment(s: Segment, t: Segment):
    "https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_2_B/judge/5781571/Python3"
    return int((ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0) and (ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0))


def _intersect_circle_segment(c: Real_Circle, s: Segment):
    if s.a == s.b:
        return int(_intersect_circle_point(c, s.a))
    h = projection(s, c.center)
    d = _distance_square_point_point(c.center, h)
    d1 = _distance_square_point_point(c.center, s.a)
    d2 = _distance_square_point_point(c.center, s.b)
    if d > c.radius_square:
        return 0
    if d == c.radius_square:
        return 1 if (ccw(s.a, s.b, h) == 0) else 0
    if d1 < c.radius_square:
        p1 = 0
    elif d1 == c.radius_square:
        p1 = 1
    else:
        p1 = 2
    if d2 < c.radius_square:
        p2 = 0
    elif d2 == c.radius_square:
        p2 = 1
    else:
        p2 = 2
    if abs(ccw(s.a, s.b, h)) == 0:
        p2 = -p2
    return int((p1 - 1) * (p2 - 1) <= 0) + int((p1 + 1) * (p2 + 1) <= 0)


def compare_roots(a: T, b: T, c: T):
    """
    -1: sqrt(a) + sqrt(b) < sqrt(c)
    0: sqrt(a) + sqrt(b) == sqrt(c)
    1: sqrt(a) + sqrt(b) > sqrt(c)
    """
    assert a >= 0
    assert b >= 0
    assert c >= 0
    c -= a + b
    if c < 0:
        return 1
    d = a * b * 4 - c * c
    if d > 0:
        return 1
    if d < 0:
        return -1
    return 0


def number_of_common_tangents(c1: Real_Circle, c2: Real_Circle):
    """
    0: include
    1: inscribe
    2: cross
    3: circumscribe
    4: separate
    (equal to number of common tangents)
    https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_7_A/judge/5781642/Python3
    """
    d = _distance_square_point_point(c1.center, c2.center)
    r1 = min(c1.radius_square, c2.radius_square)
    r2 = max(c1.radius_square, c2.radius_square)
    com = compare_roots(r1, r2, d)
    return compare_roots(d, r1, r2) + 1 if com == 1 else 3 - com


def _intersect_circle_circle(c1: Real_Circle, c2: Real_Circle):
    return 2 - abs(2 - number_of_common_tangents(c1, c2))


def _intersect_point_point(p1: Point, p2: Point):
    return int(p1 == p2)


def intersect(obj1, obj2):
    obj_types = [Real_Circle, Line, Segment, Point]
    obj_names = ["circle", "line", "segment", "point"]
    for ind1, obj_t in enumerate(obj_types):
        if isinstance(obj1, obj_t):
            break
    for ind2, obj_t in enumerate(obj_types):
        if isinstance(obj2, obj_t):
            break
    if ind1 > ind2:
        obj1, obj2 = obj2, obj1
        ind1, ind2 = ind2, ind1
    name1 = obj_names[ind1]
    name2 = obj_names[ind2]
    func = eval("_intersect_%s_%s" % (name1, name2))
    return func(obj1, obj2)


def _distance_square_line_line(l: Line, m: Line):
    return _distance_square_line_point(l, m.a) if parallel(l, m) else 0


def _distance_square_segment_point(s: Segment, p: Point):
    r = projection(s, p)
    return _distance_square_point_point(p, r) if ccw(s.a, s.b, r) == 0 else min(_distance_square_point_point(s.a, p), _distance_square_point_point(s.b, p))


def _distance_square_segment_segment(s: Segment, t: Segment):
    "https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_2_D/judge/5782899/Python3"
    if _intersect_segment_segment(s, t):
        return 0
    return min(
        _distance_square_segment_point(s, t.a),
        _distance_square_segment_point(s, t.b),
        _distance_square_segment_point(t, s.a),
        _distance_square_segment_point(t, s.b)
    )


def _distance_square_line_segment(l: Line, s: Segment):
    if _intersect_line_segment(l, s):
        return 0
    return min(
        _distance_square_segment_point(l, s.a),
        _distance_square_segment_point(l, s.b)
    )


def crosspoint(l, m):
    """It assumes that the lines (or segments) `l` and `m` has a crosspoint.
    https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_2_C/judge/5782958/Python3
    """
    A = cross(l.b - l.a, m.b - m.a)
    B = cross(l.b - l.a, l.b - m.a)
    if (A == B == 0):
        return m.a
    return m.a + (m.b - m.a) * B / A


def is_convex(polygon, pi_is_ok: bool = False):
    "https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_3_B/judge/5782989/Python3"
    n = len(polygon)
    if pi_is_ok:
        for i in range(n):
            if ccw(polygon[i - 2], polygon[i - 1], polygon[i]) == -1:
                return False
    else:
        for i in range(n):
            if ccw(polygon[i - 2], polygon[i - 1], polygon[i]) != 1:
                return False
    return True


def convex_hull(polygon, pi_is_ok: bool = False):
    "https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_4_A/judge/5783106/Python3"
    n = len(polygon)
    if n <= 2:
        return polygon
    polygon = sorted(polygon)
    ch = []
    if pi_is_ok:
        for i in range(n):
            while len(ch) >= 2 and ccw(ch[-2], ch[-1], polygon[i]) == -1:
                ch.pop()
            ch.append(polygon[i])
        t = len(ch) + 1
        for i in reversed(range(n - 1)):
            while len(ch) >= t and ccw(ch[-2], ch[-1], polygon[i]) == -1:
                ch.pop()
            ch.append(polygon[i])
    else:
        for i in range(n):
            while len(ch) >= 2 and ccw(ch[-2], ch[-1], polygon[i]) != 1:
                ch.pop()
            ch.append(polygon[i])
        t = len(ch) + 1
        for i in reversed(range(n - 1)):
            while len(ch) >= t and ccw(ch[-2], ch[-1], polygon[i]) != 1:
                ch.pop()
            ch.append(polygon[i])
    ch.pop()
    return ch


def contains(polygon, p: Point):
    """
    0: OUT
    1: ON
    2: IN
    https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_3_C/judge/5783135/Python3
    """
    in_ = 0
    for i in range(len(polygon)):
        a = polygon[i - 1] - p
        b = polygon[i] - p
        if a.y > b.y:
            a, b = b, a
        if a.y <= 0 and b.y > 0 and cross(a, b) < 0:
            in_ ^= 1
        if cross(a, b) == 0 and dot(a, b) <= 0:
            return 1
    return 2 if in_ else 0


def convex_cut(polygon, l: Line):
    """
    凸多角形の切断
    直線 l.a-l.b で切断しその左側にできる凸多角形を返す
    https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_4_C/judge/5783206/Python3
    """
    ret = []
    for i in range(len(polygon)):
        now = polygon[i - 1]
        nxt = polygon[i]
        if ccw(l.a, l.b, now) != -1:
            ret.append(now)
        if ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) == -1:
            ret.append(crosspoint(Line(now, nxt), l))
    return ret


def area(polygon):
    "https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_3_A/judge/5783215/Python3"
    A = 0
    for i in range(len(polygon)):
        A += cross(polygon[i - 1], polygon[i])
    return A / 2


def Apollonius_Circle(a: Point, b: Point, dist_a, dist_b):
    dist_a = T(dist_a)
    dist_b = T(dist_b)
    assert dist_a != dist_b  # 同じ場合はbisectionで
    asq = dist_a * dist_a
    bsq = dist_b * dist_b
    diffsq = bsq - asq
    p = (a * bsq - b * asq) / diffsq
    rsq = _distance_square_point_point(a, b) * asq * bsq / (diffsq * diffsq)
    return Real_Circle(p, rsq, True)


def bisection_of_points(a: Point, b: Point):
    c = (a + b) / 2
    return Line(c, c + Vec(a.y - b.y, b.x - a.x))


def circumscribed_circle_of_triangle(a: Point, b: Point, c: Point):
    "https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_7_C/judge/5783271/Python3"
    center = crosspoint(bisection_of_points(a, b), bisection_of_points(b, c))
    return Real_Circle(center, _distance_square_point_point(a, center), True)


def convex_diameter_square(polygon):
    "https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_4_B/judge/5783344/Python3"
    n = len(polygon)
    ist = 0
    jst = 0
    for i in range(1, n):
        if polygon[i].y > polygon[ist].y:
            ist = i
        if polygon[i].y < polygon[jst].y:
            jst = i
    maxdis = (polygon[ist] - polygon[jst]).norm_square()
    i = maxi = ist
    j = maxj = jst
    while True:
        if cross(polygon[(i + 1) % n] - polygon[i], polygon[(j + 1) % n] - polygon[j]) >= 0:
            j += 1
            j %= n
        else:
            i += 1
            i %= n
        if (polygon[i] - polygon[j]).norm_square() > maxdis:
            maxdis = (polygon[i] - polygon[j]).norm_square()
            maxi = i
            maxj = j
        if i == ist and j == jst:
            break
    return (polygon[maxi], polygon[maxj], maxdis)


def closest_pair_square(ps):
    """
    https://onlinejudge.u-aizu.ac.jp/status/users/zkou/submissions/1/CGL_5_A/judge/5785212/Python3
    https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5784360#1
    """
    assert len(ps) >= 2

    ps = sorted(ps, key=lambda p: p.x)

    def inplace_merge_cmp_y(first, middle, last):
        ret = []
        left = first
        right = middle
        while left < middle and right < last:
            if ps[left].y < ps[right].y:
                ret.append(ps[left])
                left += 1
            else:
                ret.append(ps[right])
                right += 1
        while left < middle:
            ret.append(ps[left])
            left += 1
        while right < last:
            ret.append(ps[right])
            right += 1
        ps[first:last] = ret

    def rec(left, right) -> T:
        if right - left <= 1:
            return INF
        if right - left <= 10:
            min_dist_square = INF
            for i in range(left, right):
                for j in range(i + 1, right):
                    min_dist_square = min(min_dist_square, (ps[j] - ps[i]).norm_square())
            ps[left:right] = sorted(ps[left:right], key=lambda p: p.y)
            return min_dist_square

        mid = (left + right) // 2
        x = ps[mid].x
        min_dist_square = min(rec(left, mid), rec(mid, right))
        inplace_merge_cmp_y(left, mid, right)
        near_border = []
        for i in range(left, right):
            diff = ps[i].x - x
            if diff * diff >= min_dist_square:
                continue
            for j in reversed(range(len(near_border))):
                dist = ps[i] - near_border[j]
                if dist.y * dist.y >= min_dist_square:
                    break
                min_dist_square = min(min_dist_square, dist.norm_square())
            near_border.append(ps[i])

        return min_dist_square

    return rec(0, len(ps))




N = int(input())
As = list(map(int, input().split())) + [0]

points = []
y = 0
for i in range(N + 1):
    points.append(Point(i, y))
    y += As[i]

print(closest_pair_square(points))