CF1530H Turing's Award

艾伦·图灵站在一条无限延伸、被划分为若干格子的纸带上。 格子从左到右用连续的整数编号。艾伦最初站在 $0$ 号格子上。每个格子 $x$ 的左边是 $x-1$ 号格子，右边是 $x+1$ 号格子。 每个格子可以包含一个整数，也可以为空。最初所有格子都是空的。 艾伦获得了一个长度为 $n$ 的排列 $a_1, a_2, \ldots, a_n$，该排列是从 $1$ 到 $n$ 的所有整数的一个随机排列。 在第 $1$ 时刻，整数 $a_1$ 被写入艾伦所在的 $0$ 号格子。 从第 $2$ 时刻到第 $n$ 时刻，每次操作如下：首先，艾伦可以选择留在当前格子，或者移动到左边相邻的格子，或者移动到右边相邻的格子。之后，整数 $a_i$ 被写入艾伦当前所在的格子。如果该格子已经有整数，则旧的整数会被覆盖，从此不再相关。 当第 $n$ 个数 $a_n$ 被写入某个格子后，依次从左到右收集所有格子中包含的整数，形成序列 $b$，忽略所有空格子。 图灵的奖励等于序列 $b$ 的最长上升子序列的长度。 请帮助艾伦，计算如果他采取最优策略，他能获得的奖励的最大值。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例包含两行。第一行包含一个整数 $n$（$2 \le n \le 15000$），表示排列的长度。 第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示排列的元素。 保证每个排列都是长度为 $n$ 的所有排列中等概率随机选取的。 所有测试用例中 $n$ 的总和不超过 $15000$。

对于每个测试用例，输出一个整数，表示图灵奖励的最大可能值。 本题不允许 Hack。

序列 $b$ 的最长上升子序列是指可以通过删除 $b$ 中若干（可能为零或全部）元素后得到的最长严格递增序列。 在第一个测试用例中，艾伦只有在第 $2$ 时刻可以做决策。如果艾伦留在 $0$ 号格子，$b=[2]$；如果艾伦移动到左边的 $-1$ 号格子，$b=[2, 1]$；如果艾伦移动到右边的 $1$ 号格子，$b=[1, 2]$。只有最后一种情况下，$b$ 的最长上升子序列长度为 $2$，因此答案为 $2$。 在第二个测试用例中，一种最优操作序列是：第 $2$、$3$ 时刻向左移动，第 $4$ 时刻向右移动。此时 $b=[2, 3, 4]$，其最长上升子序列长度为 $3$。 在第三个测试用例中，一种最优方式是每次都向左移动。此时 $b=[2, 1, 4, 7, 5, 6, 3]$，其最长上升子序列长度为 $4$。 在第四个测试用例中，一种最优方式是连续向右移动四次，然后向左移动一次，最后原地不动。此时 $b=[5, 2, 3, 4, 6]$。 由 ChatGPT 4.1 翻译