题目描述

在 Kick Start 2020 Round E 中（解决本题无需了解之前题目的任何内容），Sarasvati 学习了等差数组。等差数组是指至少包含 $2$ 个整数，且连续整数之间的差相等的数组。例如，$[9, 10]$、$[3, 3, 3]$ 和 $[9, 7, 5, 3]$ 是等差数组，而 $[1, 3, 3, 7]$、$[2, 1, 2]$ 和 $[1, 2, 4]$ 不是。

Sarasvati 再次有一个包含 $N$ 个非负整数的数组。数组的第 $i$ 个整数为 $A_i$。她可以最多将数组中的一个元素替换为任意（可能为负的）整数。

对于数组 $A$，Sarasvati 将子数组定义为 $A$ 中任意连续的一段。请帮助 Sarasvati 确定，通过最多替换原数组中的一个元素，她所能创建的最长等差子数组的长度。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。第二行包含 $N$ 个整数，其中第 $i$ 个整数是 $A_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最长等差子数组的长度。

3
4
9 7 5 3
9
5 5 4 5 5 5 4 5 6
4
8 5 2 0

Case #1: 4
Case #2: 6
Case #3: 4

提示

在样例 #1 中，整个数组本身就是等差数组，因此最长等差子数组即为整个数组。

在样例 #2 中，如果 Sarasvati 将第三个位置上的数改为 $5$，数组将变为 $[5, 5, 5, 5, 5, 5, 4, 5, 6]$。从第一个位置到第六个位置的子数组是最长等差子数组。

在样例 #3 中，Sarasvati 可以将最后一个位置上的数改为 $-1$，得到 $[8, 5, 2, -1]$。得到的数组是等差数组。

限制条件

$1 \le T \le 100$。

$0 \le A_i \le 10^9$。

测试集 1

$2 \le N \le 2000$。

测试集 2

最多 $10$ 个测试用例满足 $2 \le N \le 3 \times 10^5$。

其余测试用例满足 $2 \le N \le 2000$。

翻译由 DeepSeek V4 Pro 完成