AT_arc221_c.Two Deques Sorting

You are given a positive integer $N$ and a length-$N$ sequence of positive integers $A=(A_1,A_2,\dots,A_N)$.

There is also a length-$0$ sequence of positive integers $B$.

You can perform the following operation between $0$ and $N$ times, inclusive.

• Remove the first or last element of $A$, and append that element to the beginning or end of $B$.

What is the maximum number of operations you can perform, given that $B$ must be a strictly increasing sequence after the operations?

You are given $T$ test cases; solve each of them.

给你一个正整数 $N$ 和一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。

此外，还有一个长度为 $0$ 的正整数序列 $B$。

你可以执行以下操作 $0$ 至 $N$ 次（含端点）：

• 从 $A$ 的开头或末尾移除一个元素，并将该元素添加到 $B$ 的开头或末尾。

在所有操作结束后，要求 $B$ 是一个严格递增的序列。在此约束下，最多能执行多少次操作？

你将得到 $T$ 组测试用例；请分别求解每组测试用例。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入中按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
For the first test case, consider performing the operations as follows.

• Remove the first element of $A$ and append it to the end of $B$. Now $A=(1,4,1,5),B=(3)$.
• Remove the first element of $A$ and append it to the beginning of $B$. Now $A=(4,1,5),B=(1,3)$.
• Remove the first element of $A$ and append it to the end of $B$. Now $A=(1,5),B=(1,3,4)$.
• Remove the last element of $A$ and append it to the end of $B$. Now $A=(1),B=(1,3,4,5)$.

The final $B=(1,3,4,5)$ is a strictly increasing sequence, and the number of operations is $4$. It is impossible to perform five operations while satisfying the condition, so the answer is $4$.

For the second test case, note that $B=(1,2,2)$ is not a strictly increasing sequence.

Constraints

• $1\le T\le 3\times 10^5$
• $1\le N\le 3\times 10^5$
• $1\le A_i \le N$ $(1\leq i\leq N)$
• The sum of $N$ over all test cases is at most $3\times 10^5$.
• All input values are integers.

样例 1 解释：
对于第一个测试用例，考虑按如下方式执行操作：

• 移除 $A$ 的第一个元素，并将其追加到 $B$ 的末尾。此时 $A=(1,4,1,5)$，$B=(3)$。
• 移除 $A$ 的第一个元素，并将其插入到 $B$ 的开头。此时 $A=(4,1,5)$，$B=(1,3)$。
• 移除 $A$ 的第一个元素，并将其追加到 $B$ 的末尾。此时 $A=(1,5)$，$B=(1,3,4)$。
• 移除 $A$ 的最后一个元素，并将其追加到 $B$ 的末尾。此时 $A=(1)$，$B=(1,3,4,5)$。

最终得到的 $B=(1,3,4,5)$ 是一个严格递增序列，且操作次数为 $4$。在满足条件的前提下无法执行五次操作，因此答案为 $4$。

对于第二个测试用例，注意 $B=(1,2,2)$ 并非严格递增序列。

约束条件

• $1\le T\le 3\times 10^5$
• $1\le N\le 3\times 10^5$
• $1\le A_i \le N$ $(1\leq i\leq N)$
• 所有测试用例的 $N$ 之和不超过 $3\times 10^5$。
• 所有输入值均为整数。