/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
正整数 N と，長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます．
また，長さ 0 の正整数列 B があります．
あなたは，以下の操作を 0 回以上 N 回以下行うことができます．
- A の先頭または末尾の要素を削除し，その要素を B の先頭または末尾に追加する．
操作終了後に B が狭義単調増加列である必要があるとき，最大で何回操作を行うことができますか．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 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 以下
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる．
N A_1 A_2 \ldots A_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ．
入力例 1
3 5 3 1 4 1 5 3 2 2 1 16 3 4 5 7 12 15 1 15 16 8 14 2 16 14 9 2
出力例 1
4 2 11
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 回です．条件を満たすように 5 回操作することはできないので，答えは 4 です．
2 番目のテストケースについて，B=(1,2,2) は狭義単調増加列でないことに注意してください．
Score : 800 points
Problem Statement
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.
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.
Input
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
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
3 5 3 1 4 1 5 3 2 2 1 16 3 4 5 7 12 15 1 15 16 8 14 2 16 14 9 2
Sample Output 1
4 2 11
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.