CF1530H.Turing's Award

Alan Turing is standing on a tape divided into cells that is infinite in both directions.

Cells are numbered with consecutive integers from left to right. Alan is initially standing in cell $0$. Every cell $x$ has cell $x - 1$ on the left and cell $x + 1$ on the right.

Each cell can either contain an integer or be empty. Initially all cells are empty.

Alan is given a permutation $a_1, a_2, \ldots, a_n$ of integers from $1$ to $n$ that was chosen uniformly at random among all permutations of length $n$.

At time $1$, integer $a_1$ is written down into cell $0$ where Alan is located.

At each time $i$ from $2$ to $n$ inclusive, the following happens. First, Alan decides whether to stay in the same cell he's currently in, move to the neighboring cell on the left, or move to the neighboring cell on the right. After that, integer $a_i$ is written down into the cell where Alan is located. If that cell already contained some integer, the old integer is overwritten and irrelevant from that moment on.

Once $a_n$ is written down into some cell at time $n$, sequence $b$ of all integers contained in the cells from left to right is formed. Empty cells are ignored.

Turing's award is equal to the length of the longest increasing subsequence of sequence $b$.

Help Alan and determine the largest possible value of his award if he acts optimally.

阿兰·图灵站在一条向左右两个方向无限延伸的纸带上，纸带被划分为若干个单元格。

单元格从左到右用连续整数编号。阿兰初始时位于第 $0$ 号单元格。对任意单元格 $x$，其左侧为单元格 $x - 1$，右侧为单元格 $x + 1$。

每个单元格要么包含一个整数，要么为空。初始时所有单元格均为空。

阿兰被给定一个长度为 $n$ 的排列 $a_1, a_2, \ldots, a_n$，该排列是 $1$ 到 $n$ 的所有排列中均匀随机选取的。

在时刻 $1$，整数 $a_1$ 被写入阿兰当前所在单元格（即第 $0$ 号单元格）。

对每个时刻 $i = 2, 3, \ldots, n$，依次发生以下操作：首先，阿兰决定保持在当前单元格不动、向左移动至相邻单元格，或向右移动至相邻单元格；随后，整数 $a_i$ 被写入阿兰当前所在的单元格。若该单元格已含有某个整数，则旧整数被覆盖，从此不再相关。

当在时刻 $n$ 将 $a_n$ 写入某个单元格后，将从左到右收集所有非空单元格中的整数，构成序列 $b$（忽略所有空单元格）。

图灵奖的数值等于序列 $b$ 的最长递增子序列（LIS）的长度。

请帮助阿兰，求出他在最优策略下所能获得的最大可能的图灵奖值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

Each test case is given in two lines. The first line of each test case contains a single integer $n$ ($2 \le n \le 15\,000$) — the length of the permutation given to Alan.

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of the permutation.

It is guaranteed that the permutation was chosen uniformly at random among all permutations of the corresponding length.

The sum of $n$ over all test cases does not exceed $15\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是测试用例的描述。

每个测试用例由两行给出。每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 15\,000$）——即给定 Alan 的排列长度。

第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——即该排列的元素。

保证该排列是在对应长度的所有排列中均匀随机选取的。

所有测试用例的 $n$ 值之和不超过 $15\,000$。

For each test case output a single integer — the largest possible value of Turing's award.

Hacks are not allowed for this problem.

对于每个测试用例，输出一个整数——图灵奖的最大可能值。

本题不允许 hack。

Longest increasing subsequence of sequence $b$ is the longest increasing sequence that can be obtained from $b$ by deletion of several (possibly, zero or all) elements.

In the first test case, Alan can make a decision only at time $2$. If Alan stays in cell $0$, sequence $b$ will be equal to $[2]$. If Alan moves to the left, to cell $-1$, sequence $b$ will be equal to $[2, 1]$. If Alan moves to the right, to cell $1$, sequence $b$ will be equal to $[1, 2]$. Only in the last case the length of the longest increasing subsequence of $b$ is $2$, therefore, the answer is equal to $2$.

In the second test case, one of the optimal sequences of actions looks as follows: move to the left at times $2$ and $3$, and move to the right at time $4$. Then sequence $b$ will be equal to $[2, 3, 4]$, and the length of its longest increasing subsequence is $3$.

In the third test case, one of the best ways is to always move to the left. Then sequence $b$ will be equal to $[2, 1, 4, 7, 5, 6, 3]$, and the length of its longest increasing subsequence is $4$.

In the fourth test case, one of the best ways is to move to the right four times, then move to the left once, and stay in the same cell once. Sequence $b$ will be equal to $[5, 2, 3, 4, 6]$.

序列 $b$ 的最长递增子序列（LIS）是指通过从 $b$ 中删除若干（可能为零个或全部）元素后所能得到的最长递增序列。

在第一个测试用例中，Alan 仅能在时刻 $2$ 做出决策。若 Alan 停留在单元格 $0$，则序列 $b$ 将为 $[2]$；若 Alan 向左移动至单元格 $-1$，则序列 $b$ 将为 $[2, 1]$；若 Alan 向右移动至单元格 $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]$。