关键变形 —— 拆解绝对值的和

绝对值的和 |a| + |b| 有一个重要的数学性质：

对于任意实数 a,b，等式|a| + |b| = max{ |a+b|, |a-b| }恒成立。

我们可以通过分类讨论（基于 a 和 b 的符号组合）验证这个性质：

1. 当 a ≥ 0, b ≥ 0 时：

|a| + |b| = a + b，而 a + b = |a+b|（因为两非负数之和仍非负）。

此时 |a-b| 表示两数的 “差值”，必然小于等于两数的 “和值”（即 |a-b| ≤ a+b），因此 |a| + |b| = |a+b|。

2. 当 a ≥ 0, b ≤ 0 时：

|a| + |b| = a + (-b)（因为 b ≤ 0，其绝对值为 -b），而 a - b = |a - b|（因为 a ≥ 0、-b ≥ 0，两者之和非负）。

此时 |a+b| 表示两数的 “抵消后的值”，必然小于等于两数的 “绝对值之和”（即 |a+b| ≤ a - b），因此 |a| + |b| = |a - b|。

3. 其他符号组合（如 a ≤ 0, b ≥ 0 或 a ≤ 0, b ≤ 0）：

可参考上述逻辑同理验证。例如 a ≤ 0, b ≥ 0 与 “a ≥ 0, b ≤ 0” 对称，a ≤ 0, b ≤ 0 与 “a ≥ 0, b ≥ 0” 对称，最终均满足 |a| + |b| = max{ |a+b|, |a-b| }。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();  // 消耗掉换行符
        String[] parts = sc.nextLine().split(" ");
        long[] A = new long[n];
        for (int i = 0; i < n; i++) {
            A[i] = Long.parseLong(parts[i]);
        }

        // 计算x = i² + A_i²的最大最小值
        long maxX = Long.MIN_VALUE;
        long minX = Long.MAX_VALUE;
        // 计算y = i² - A_i²的最大最小值
        long maxY = Long.MIN_VALUE;
        long minY = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            // 注意索引是从1开始的
            long index = i + 1;
            long indexSq = index * index;
            long aSq = A[i] * A[i];

            long x = indexSq + aSq;
            long y = indexSq - aSq;

            maxX = Math.max(maxX, x);
            minX = Math.min(minX, x);
            maxY = Math.max(maxY, y);
            minY = Math.min(minY, y);
        }

        // 最大距离是两个差值中的较大者
        long maxDist = Math.max(maxX - minX, maxY - minY);
        System.out.println(maxDist);
    }
}