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)^2 + g(i, j)^2. Function g is calculated by the following pseudo-code:



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;

}



Find a value min_{i} ≠ j  f(i, j).

Probably by now Iahub already figured out the solution to this problem. Can you?


-----Input-----

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^4 ≤ a[i] ≤ 10^4). 


-----Output-----

Output a single integer — the value of min_{i} ≠ j  f(i, j).


-----Examples-----
Input
4
1 0 0 -1

Output
1

Input
2
1 -1

Output
2

Difficulty: competition

Starter code:

Solutions:
from sys import stdin, stdout

INF = int(1e9)


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


def distance(p1, p2):
    x = p1.x - p2.x
    y = p1.y - p2.y
    return x*x + y*y


def bruteForce(point_set, left, right):
    min_dist = INF
    for i in range(left, right):
        for j in range(i+1, right):
            min_dist = min(min_dist, distance(point_set[i], point_set[j]))
    return min_dist


def stripClosest(point_set, left, right, mid, min_dist):
    point_mid = point_set[mid]
    splitted_points = []
    for i in range(left, right):
        if (point_set[i].x - point_mid.x) ** 2 <= min_dist:
            splitted_points.append(point_set[i])
    splitted_points.sort(key=lambda point: point.y)
    l = len(splitted_points)
    smallest = INF
    for i in range(l):
        for j in range(i+1, l):
            if (splitted_points[i].y - splitted_points[j].y) ** 2 >= min_dist:
                break
            d = distance(splitted_points[i], splitted_points[j])
            smallest = min(smallest, d)
    return smallest


def closestUtil(point_set, left, right):
    if right - left <= 3:
        return bruteForce(point_set, left, right)

    mid = (left + right) // 2
    dist_left = closestUtil(point_set, left, mid)
    dist_right = closestUtil(point_set, mid+1, right)
    dist_min = min(dist_left, dist_right)

    return min(dist_min, stripClosest(point_set, left, right, mid, dist_min))


n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))

pref = [0]
for i in range(n):
    pref.append(pref[i] + a[i])

point_set = []
for i in range(n):
    point_set.append(Point(i, pref[i+1]))

ans = closestUtil(point_set, 0, n)
stdout.write(str(ans))


import sys
sys.setrecursionlimit(100000)
INF = 1e9
 
 
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
 
def distance(p1, p2):
    x = p1.x - p2.x
    y = p1.y - p2.y
    return (x ** 2 + y ** 2) ** 0.5
 
 
def brute_force(point_set, left, right):
    min_dist = INF
    for i in range(left, right):
        for j in range(i + 1, right):
            min_dist = min(min_dist, distance(point_set[i], point_set[j]))
    return min_dist
 
 
def strip_closest(point_set, left, right, mid, dist_min):
    point_mid = point_set[mid]
    splitted_points = []
    for i in range(left, right):
        if abs(point_set[i].x - point_mid.x) <= dist_min:
            splitted_points.append(point_set[i])
    splitted_points.sort(key=lambda p: p.y)
 
    smallest = INF
    l = len(splitted_points)
    for i in range(0, l):
        for j in range(i + 1, l):
            if not (splitted_points[j].y - splitted_points[i].y) < dist_min:
                break
            d = distance(splitted_points[i], splitted_points[j])
            smallest = min(smallest, d)
    return smallest
 
 
def closest_util(point_set, left, right):
    if right - left <= 3:
        return brute_force(point_set, left, right)
    mid = (right + left) // 2
    dist_left = closest_util(point_set, left, mid)
    dist_right = closest_util(point_set, mid + 1, right)
    dist_min = min(dist_left, dist_right)
    return min(dist_min, strip_closest(point_set, left, right, mid, dist_min))
 
 
n = int(input())
a = list(map(int, input().split()))
point_set = []
for i in range(n):
    if (i > 0):a[i] += a[i - 1]
    point_set.append(Point(i , a[i]))

point_set.sort(key=lambda a: a.x)
ans = closest_util(point_set, 0, n)
print('%.0f' % (ans * ans))


import sys
max_Int = int(1e9)

class splitFeature:
    def __init__(self, position, value):
        self.position = position
        self.value = value

def bruteForce(features, left, right):
    min_distance = max_Int
    for i in range(left, right):
        for j in range(i+1, right):
            min_distance = min(min_distance,
                               (features[i].position - features[j].position)**2 + (features[i].value - features[j].value)**2)
    return min_distance

def enhanceData(features, left, right, mid, min_distance):
    selected_population = []
    for i in range(left, right):
        if (features[i].position - features[mid].position) ** 2 <= min_distance:
            selected_population.append(features[i])
    selected_population.sort(key = lambda x: x.value)
    l = len(selected_population)
    result = max_Int
    for i in range(l):
        for j in range(i+1, l):
            if (selected_population[i].value - selected_population[j].value) ** 2 >= min_distance:
                break
            distance = (selected_population[i].position - selected_population[j].position)**2 + (selected_population[i].value - selected_population[j].value)**2
            result = min(result, distance)
    return result

def analyzeData(features, left, right):
    if right - left <= 3:
        return bruteForce(features, left, right)
    mid = (left + right) // 2
    min_distance = min(analyzeData(features, left, mid), 
                       analyzeData(features, mid+1, right))
    return min(min_distance, 
               enhanceData(features, left, right, mid, min_distance))

def main():
    n = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    features = []
    for i in range(n):
        if (i > 0):
            A[i] += A[i-1]
        features.append(splitFeature(i , A[i]))
    sys.stdout.write(str(analyzeData(features, 0, n)))

main()


import sys
max_Int = int(1e9)

class splitFeature:
    def __init__(self, position, value):
        self.position = position
        self.value = value

def bruteForce(features, left, right):
    min_distance = max_Int
    for i in range(left, right):
        for j in range(i+1, right):
            min_distance = min(min_distance,
                               (features[i].position - features[j].position)**2 + (features[i].value - features[j].value)**2)
    return min_distance

def enhanceData(features, left, right, mid, min_distance):
    selected_population = []
    for i in range(left, right):
        if (features[i].position - features[mid].position) ** 2 <= min_distance:
            selected_population.append(features[i])
    selected_population.sort(key = lambda x: x.value)
    l = len(selected_population)
    result = max_Int
    for i in range(l):
        for j in range(i+1, l):
            if (selected_population[i].value - selected_population[j].value) ** 2 >= min_distance:
                break
            distance = (selected_population[i].position - selected_population[j].position)**2 + (selected_population[i].value - selected_population[j].value)**2
            result = min(result, distance)
    return result

def analyzeData(features, left, right):
    if right - left <= 3:
        return bruteForce(features, left, right)
    mid = (left + right) // 2
    min_distance = min(analyzeData(features, left, mid), 
                       analyzeData(features, mid+1, right))
    return min(min_distance, 
               enhanceData(features, left, right, mid, min_distance))

def main():
    n = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    features = []
    for i in range(n):
        if (i > 0):
            A[i] += A[i-1]
        features.append(splitFeature(i , A[i]))
    sys.stdout.write(str(analyzeData(features, 0, n)))

main() #optimizeCode


import sys
max_Int = int(1e9)

class splitFeature:
    def __init__(self, position, value):
        self.position = position
        self.value = value

def bruteForce(features, left, right):
    min_distance = max_Int
    for i in range(left, right):
        for j in range(i+1, right):
            min_distance = min(min_distance,
                               (features[i].position - features[j].position)**2 + (features[i].value - features[j].value)**2)
    return min_distance

def enhanceData(features, left, right, mid, min_distance):
    selected_population = []
    for i in range(left, right):
        if (features[i].position - features[mid].position) ** 2 <= min_distance:
            selected_population.append(features[i])
    selected_population.sort(key = lambda x: x.value)
    l = len(selected_population)
    result = max_Int
    for i in range(l):
        for j in range(i+1, l):
            if (selected_population[i].value - selected_population[j].value) ** 2 >= min_distance:
                break
            distance = (selected_population[i].position - selected_population[j].position)**2 + (selected_population[i].value - selected_population[j].value)**2
            result = min(result, distance)
    return result

def analyzeData(features, left, right):
    if right - left <= 3:
        return bruteForce(features, left, right)
    mid = (left + right) // 2
    min_distance = min(analyzeData(features, left, mid), 
                       analyzeData(features, mid+1, right))
    return min(min_distance, 
               enhanceData(features, left, right, mid, min_distance))

def main():
    n = int(input())
    A = list(map(int, input().split()))
    features = []
    for i in range(n):
        if (i > 0):
            A[i] += A[i-1]
        features.append(splitFeature(i , A[i]))
    print(analyzeData(features, 0, n))

main()