← 返回题目列表

Codeforces · 2236/E

E. 友好的礼物

中文机器翻译题面 查看原题

Arseniy 决定让他的朋友 Dabir 和 Egor 开心。为此,他决定给他们每个人一组数字 相同长度。调用数组 $$$b$$$ 好 如果可以重新排列其元素,以便对于所有 $$$i \gt 1$$$ 条件 $$$b_i - b_{i - 1} = 1$$$ 成立。

Arseniy 希望 Dabir 和 Egor 能够使用这些阵列。为此,必须满足以下条件:

  1. 每个给定的数组是 好.
  2. 如果您在另一个数组之后写入一个数组(换句话说,将它们连接起来),则生成的数组也是 好.

Arseniy 已经有一个长度为 $$$n$$$ 的数组 $$$a$$$。他计划从$$$a$$$中切出两个数组,即选择两个不重叠的子段 相同长度。帮助阿尔森尼确定 最大 结果数组的可能长度。

输入

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - 最大 数组的可能长度。

示例

输入
复制

7
1
1
2
1 2
3
2 1 1
4
2 1 4 3
5
1 2 4 5 3
6
3 2 1 6 5 4
10
1 1 2 3 4 1 6 5 7 8

输出
复制

0
1
1
2
1
3
4

注意

在第一个示例中,不可能选择 $$$2$$$ 数组,因此答案是 $$$0$$$。

在第二个示例中,所选数组的最大长度为 $$$1$$$。可以选择数组 [$$$1$$$] 和 [$$$2$$$]。

在第四个示例中,所选数组的最大长度为$$$2$$$。您可以选择数组 [$$$2, 1$$$] 和 [$$$4, 3$$$]。

在第五个示例中,所选数组的最大长度为$$$1$$$。选择数组的一种方法是 [$$$1$$$] 和 [$$$2$$$]。其他方法是数组 [$$$2$$$] 和 [$$$3$$$]、[$$$3$$$] 和 [$$$4$$$] 或 [$$$4$$$] 和 [$$$5$$$]。