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

Source: codeforces | Difficulty: HARD
Tags: Geometry

Data structures

Divide and conquer


Solutions:
import sys
max_Int = int(1000000000.0)

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
sys.setrecursionlimit(100000)
INF = 1000000000.0

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))


from sys import stdin, stdout
INF = int(1000000000.0)

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 os
import math
cumsum = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
n = cumsum[0]
cumsum[0] = 0
for i in range(n):
	cumsum[i + 1] += cumsum[i]

def work(besta, i, sqrtbesta, lowerbound, upperbound, cumsumi):
	for j in range(i + 1, min(n, i - 1 + sqrtbesta) + 1):
		if lowerbound < cumsum[j] < upperbound and (j - i) ** 2 + (cumsum[j] - cumsumi) ** 2 < besta:
			besta = (j - i) ** 2 + (cumsum[j] - cumsumi) ** 2
	return besta
besta = 10100 ** 2
for i in range(1, n):
	sqrtbesta = int(math.sqrt(besta)) + 1
	lowerbound = -sqrtbesta + cumsum[i]
	upperbound = sqrtbesta + cumsum[i]
	besta = work(besta, i, sqrtbesta, lowerbound, upperbound, cumsum[i])
print(besta)