CF2236E Friendly Gifts

Arseniy 想让他的朋友 Dabir 和 Egor 开心。为此，他打算分别送给他们一个长度相同的数列。一个数组 $b$ 被称为“好数组”，如果它的元素可以重新排列，使得对于所有 $i > 1$，都有 $b_i - b_{i-1} = 1$ 成立。 Arseniy 希望 Dabir 和 Egor 能够用这些数组一起玩。为此，必须满足以下条件： 1. 给出的每一个数组都是好数组。 2. 如果你将这两个数组首尾相接拼接在一起，得到的新数组依然是好数组。 Arseniy 已经有一个长度为 $n$ 的数组 $a$。他打算从 $a$ 中裁剪出这两个数组，也就是说，从 $a$ 中选出两个长度相同且互不重叠的子段。请你帮助 Arseniy 确定这两个最终数组的最大可能长度。

第一行包含一个整数 $t$ $(1 \le t \le 1000)$，表示测试用例的数量。 接下来是 $t$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 6000)$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le n)$。 保证所有测试用例中 $n$ 的总和不超过 $6000$。

对于每个测试用例，输出一个整数，表示可以选出的数组的最大长度。

在第一个样例中，不可能选出 2 个数组，所以答案是 $0$。 在第二个样例中，最大可选数组长度是 $1$。可以选择数组 \[ $1$ \] 和 \[ $2$ \]。 在第四个样例中，最大可选数组长度是 $2$。可以选择数组 \[ $2, 1$ \] 和 \[ $4, 3$ \]。 在第五个样例中，最大可选数组长度是 $1$。一种选择方法是数组 \[ $1$ \] 和 \[ $2$ \]；其他方法还包括数组 \[ $2$ 和 $3$ \]、\[$3$ 和 $4$\]，或者 \[$4$ 和 $5$\]。 由 ChatGPT 5 翻译