D. Excellent Splitting
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little H has a permutation $$$P$$$, and he wants to split $$$P$$$ into sequence $$$A$$$ and sequence $$$B$$$.

Specifically, Little H will take several elements from $$$P$$$ in order and place them into sequence $$$A$$$, while the remaining elements will form another sequence $$$B$$$ in order.

For example, if $$$P = [1,2,3,4,5]$$$, he can split $$$P$$$ into $$$A = [1,3,5], B = [2,4]$$$.

He is very fond of increasing subsequences and decreasing subsequences. Define $$$f(A)$$$ as the length of the longest increasing subsequence of $$$A$$$, and $$$g(B)$$$ as the length of the longest decreasing subsequence of $$$B$$$. You need to tell him the maximum value of $$$f(A) + g(B)$$$.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 2\cdot 10^5)$$$, indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$, representing the length of the permutation $$$P$$$.

The second line contains $$$n$$$ integers $$$P_1,P_2,\ldots ,P_n$$$ $$$(1\leq P_i \leq n)$$$, ensuring that $$$P_i$$$ is a permutation.

The sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output a single line containing an integer, representing the maximum value of $$$f(A) + g(B)$$$.

Example
Input
3
5
3 5 1 4 2
4
1 2 4 3
5
3 5 2 1 4
Output
4
4
5