题解 | 最大 FST 距离

# # 方法一：暴力解法，但超时
# n = int(input())
# num_list = list(map(int, input().split()))

# max_FST = 0
# for i in range(n):    # 任意两点循环计算，将最大值通过max()选出
#     for j in range(n):
#         max_FST = max(max_FST, abs((i+1)**2-(j+1)**2)+abs(num_list[i]**2-num_list[j]**2))

# print(max_FST)

# 方法二：设i^2为Xi，设Ai^2为Yi，则原式可化为dist=|(Xi-Xj)|+|(Yi-Yj)|
# 若(Xi, Yi)是坐标点，则我们要求两点的横纵坐标之差的绝对值的和
# 将绝对值展开得到四个式子
# 1:(Xi±Yi)-(Xj±Yj)  
# 2:(-Xi±Yi)-(-Xj±Yj)    观察可知，第二组式子可由第一组式子的基础上添加负号得来
# 故选择第一组式子，1:(Xi+Yi)-(Xj+Yj)    2:(Xi-Yi)-(Xj-Yj)
# 而上述两个式子中只出现了两种元素：Xi+Yi和Xi-Yi
# 故只需求出两者各自的max和min，相减取最大值即可
n = int(input())
num_list = list(map(int, input().split()))

jia_list = []
jian_list = []
for i in range(n):    # 存入x+y和x-y的所有值
    x = (i + 1) ** 2
    y = num_list[i] ** 2
    jia_list.append(x + y)
    jian_list.append(x - y)

# 根据两个式子计算一个最大的
max_FST = max(max(jia_list) - min(jia_list), max(jian_list) - min(jian_list)) 
print(max_FST)