Turing's Award
Contest: Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))
Difficulty rating: 3400
Tags: data structures, dp

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.

Input format:
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$$$.

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

Hacks are not allowed for this problem.

Constraints:
Time limit: 10.0 s
Memory limit: 512.0 MB

Note:
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]$$$.

Example input:
4
2
1 2
4
4 1 2 3
7
3 6 5 7 4 1 2
7
5 2 3 7 6 1 4

Example output:
2
3
4
4

Editorial:
Let's look at Alan's moves in reverse. The process can be reformulated as follows. Initially, $$$a_n$$$ is written down into the cell where Alan is located. Then, for each $$$i$$$ from $$$n-1$$$ down to $$$1$$$, first Alan decides whether to stay or move to a neighboring cell, and then $$$a_i$$$ is written down into Alan's cell only if the cell is empty. This way, it's easier to reason about the process since numbers never get overwritten.
The state at any moment can be described by the current sequence $$$b$$$ and Alan's position inside this sequence. The only way we can change $$$b$$$ is by appending a number to either end.
Suppose we have decided which elements of the permutation appear in the final sequence $$$b$$$, and for each element, whether it gets appended to the front or to the back. Let's call these elements useful. As a special case, $$$a_n$$$ is always useful. Two things to notice here:
• We don't care about intermediate Alan's positions, as long as he has enough time to move between consecutive useful elements. For example, suppose $$$a_i$$$ gets appended to the front of $$$b$$$ (the other case is symmetrical), and there are exactly $$$k$$$ useful elements among $$$a_i, a_{i+1}, \ldots, a_n$$$. Let $$$a_j$$$ be the "next" useful element, that is, $$$j < i$$$ and there are no useful elements between $$$a_j$$$ and $$$a_i$$$.   If $$$a_j$$$ should be appended to the front of $$$b$$$, Alan can just stay in the same cell for elements $$$a_{i-1}, a_{i-2}, \ldots, a_{j+1}$$$, and then move to the left to append $$$a_j$$$. Here, Alan is always in time.  If $$$a_j$$$ should be appended to the back of $$$b$$$, Alan has to move to the other end of $$$b$$$, and he needs to make $$$k$$$ steps to the right. This is possible if and only if $$$i - j \ge k$$$.
• If $$$a_j$$$ should be appended to the front of $$$b$$$, Alan can just stay in the same cell for elements $$$a_{i-1}, a_{i-2}, \ldots, a_{j+1}$$$, and then move to the left to append $$$a_j$$$. Here, Alan is always in time.
• If $$$a_j$$$ should be appended to the back of $$$b$$$, Alan has to move to the other end of $$$b$$$, and he needs to make $$$k$$$ steps to the right. This is possible if and only if $$$i - j \ge k$$$.
• Consider a useful element that neither belongs to the LIS (longest increasing subsequence) of $$$b$$$, nor is $$$a_n$$$. We can always change this element's status to "not useful", and it won't harm us in any way. Thus, we can assume that all of the useful elements, except for maybe $$$a_n$$$, belong to the LIS.
Let's casework on whether $$$a_n$$$ belongs to the LIS. From now on, we will assume that $$$a_n$$$ does belong to the LIS. However, the other case differs just slightly.
Armed with the above observations, we can solve the problem using dynamic programming:
• $$$f_L(k, i)$$$: suppose $$$a_i$$$ is a useful element that gets appended to the front, and there are $$$k$$$ useful elements among $$$a_i, a_{i+1}, \ldots, a_n$$$. Then $$$f_L(k, i)$$$ is the smallest possible value of the element at the back of the LIS.
• $$$f_R(k, i)$$$: suppose $$$a_i$$$ is a useful element that gets appended to the back, and there are $$$k$$$ useful elements among $$$a_i, a_{i+1}, \ldots, a_n$$$. Then $$$f_R(k, i)$$$ is the largest possible value of the element at the front of the LIS.
Note that some DP states might be unreachable: in this case, we set $$$f_L(\ldots)$$$ to $$$+\infty$$$ and $$$f_R(\ldots)$$$ to $$$-\infty$$$.
Consider transitions from $$$f_L(k, i)$$$ (transitions from $$$f_R(k, i)$$$ are similar):
• For any $$$j < i$$$ such that $$$a_j < a_i$$$, we can set $$$f_L(k + 1, j)$$$ to $$$f_L(k, i)$$$.
• For any $$$j \le i - k$$$ such that $$$a_j > f_L(k, i)$$$, we can set $$$f_R(k + 1, j)$$$ to $$$a_i$$$.
Thus, we can transition from $$$f(k, \ldots)$$$ to $$$f(k + 1, \ldots)$$$ in $$$O(n^2)$$$ time. We can optimize it to $$$O(n \log n)$$$ if we sweep through the permutation in reverse order ($$$i = n, n - 1, \ldots, 1$$$) and maintain a segment tree for minimum/maximum indexed with element values.
The answer to the problem is the largest $$$k$$$ such that $$$f_L(k, i)$$$ or $$$f_R(k, i)$$$ is a reachable state for some $$$i$$$. The complexity of our solution is thus $$$O(kn \log n)$$$.
Finally, note that the part of $$$b$$$ to the left of $$$a_n$$$ forms an increasing subsequence of $$$a$$$, and the part of $$$b$$$ to the right of $$$a_n$$$ forms a decreasing subsequence of $$$a$$$. It is well-known that the expected length of the longest increasing/decreasing subsequence in a random permutation is $$$O(\sqrt{n})$$$. Therefore, our solution works in $$$O(n^{1.5} \log n)$$$ on average.