题解 | 最大 FST 距离

# import sys
# n = int(input())
# num_list = list(map(int,sys.stdin.readline().strip().split()))
# list2 = []
# def dist(i,j):
#     return (abs((i**2)-(j**2)) + abs((num_list[i-1]**2)-(num_list[j-1]**2)))
# for i in range(n+1):
#     for j in range(n+1):
#         list2.append(dist(i,j))
# print(max(list2))
# 然后狠狠超时

n = int(input())
A = list(map(int, input().split()))

# ===================== 核心公式推理 =====================
# 题目要求：求最大的 |i² - j²| + |Ai² - Aj²|
# 我们对公式变形：
#
# 原式 = |i² - j²| + |Ai² - Aj²|
#
# 利用代数恒等式：|a| + |b| = max( |a+b| , |a−b| )
# 代入 a = i²-j² , b = Ai²-Aj²
#
# 所以：
# |i²-j²| + |Ai²-Aj²|
# = max( | (i²+Ai²) − (j²+Aj²) | , | (i²−Ai²) − (j²−Aj²) | )
#
# 这意味着：最大值只来自两个新数组的「最大差值」
# 数组1：s1 = i² + Ai²
# 数组2：s2 = i² − Ai²
#
# 任意数组的最大差值 = 最大值 − 最小值
# 所以答案 = max( max(s1)-min(s1), max(s2)-min(s2) )
# ======================================================

# 初始化四个极值变量
max1 = -float('inf')  # s1 的最大值
min1 = float('inf')   # s1 的最小值
max2 = -float('inf')  # s2 的最大值
min2 = float('inf')   # s2 的最小值

# 一次遍历，O(n) 复杂度，完美不超时
for idx in range(n):
    # 题目下标从 1 开始，所以 i = idx + 1
    i = idx + 1
    ai = A[idx]
    
    # 计算两个关键值（推理出来的核心变量）
    s1 = i * i + ai * ai  # 第一个组合：i² + Ai²
    s2 = i * i - ai * ai  # 第二个组合：i² − Ai²
    
    # 更新 s1 的最大、最小值
    if s1 > max1:
        max1 = s1
    if s1 < min1:
        min1 = s1
    
    # 更新 s2 的最大、最小值
    if s2 > max2:
        max2 = s2
    if s2 < min2:
        min2 = s2

# 最终答案：两个差值取最大
ans = max(max1 - min1, max2 - min2)
print(ans)