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 random
import itertools
from collections import defaultdict
from math import sqrt, ceil
from typing import Tuple, List, Sequence, Dict, Callable


class Point:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __sub__(self, other: 'Point') -> 'Point':
        return Point(self.x - other.x, self.y - other.y)

    def norm_sq(self) -> int:
        return self.x**2 + self.y**2


def dist_sq(p1: Point, p2: Point) -> int:
    i, j = p1.x, p2.x
    g = sums[max(i, j)] - sums[min(i, j)]
    return ((i - j)**2 + g**2)**2
    # return (p1 - p2).norm_sq()


def scan_point(s: str) -> Point:
    return Point(*map(int, s.split(maxsplit=1)))


def brute_force(ps: List[Point]) -> Tuple[Point, Point]:
    return min(((ps[i], ps[j]) for i in range(len(ps))
                for j in range(i + 1, len(ps))),
               key=lambda p: dist_sq(*p))


SqID = Tuple[int, int]


def break_into_squares(d: float,
                       points: List[Point]) -> Dict[SqID, List[Point]]:
    sqs = defaultdict(list)
    for p in points:
        x1, y1 = int(p.x // d), int(p.y // d)
        sqs[(x1, y1)].append(p)
    return sqs


def get_adjacent(key: SqID) -> Sequence[SqID]:
    """includes the key"""
    x, y = key
    return ((x + dx, x + dy) for dx in (-1, 0, 1) for dy in (-1, 0, 1))


def find_min_dist(points: List[Point]) -> Tuple[Point, Point]:
    n = len(points)
    sample = random.sample(points, ceil(sqrt(n)))

    global_arg = brute_force(sample)
    global_best = dist_sq(*global_arg)
    d = sqrt(global_best)
    sqs = break_into_squares(d, points)

    for key in sqs.keys():
        merged = list(
            itertools.chain.from_iterable(
                sqs.get(key_, []) for key_ in get_adjacent(key)))
        if len(merged) <= 1:
            continue
        local_arg = brute_force(merged)
        local_best = dist_sq(*local_arg)
        if global_best > local_best:
            global_best, global_arg = local_best, local_arg

    return global_arg


sums = [0]


def main(read: Callable[[], str], write: Callable[..., None]):
    n = int(read())
    for a in map(int, read().split()):
        sums.append(sums[-1] + a)
    points = [Point(i + 1, sums[i + 1]) for i in range(n)]
    p1, p2 = find_min_dist(points)
    # i1, i2 = sorted((points.index(p1), points.index(p2)))
    d = sqrt(dist_sq(p1, p2))
    write(int(d))


if __name__ == '__main__':
    main(input, print)
    # task = 'rendezvous'
    # inpath, outpath = task + '.in', task + '.out'
    # with open(inpath, 'r') as infile, open(outpath, 'w') as outfile:
    #     read = lambda: infile.readline()
    #     write = lambda *args, **kwargs: print(*args, **kwargs, file=outfile)
    #     main(read, write)
