AT_arc221_c [ARC221C] 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.

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 $

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

### Sample Explanation 1 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.