AT_arc221_c [ARC221C] Two Deques Sorting

正整数 $ N $ と，長さ $ N $ の正整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます． また，長さ $ 0 $ の正整数列 $ B $ があります． あなたは，以下の操作を $ 0 $ 回以上 $ N $ 回以下行うことができます． - $ A $ の先頭または末尾の要素を削除し，その要素を $ B $ の先頭または末尾に追加する． 操作終了後に $ B $ が狭義単調増加列である必要があるとき，最大で何回操作を行うことができますか． $ T $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

各テストケースに対する答えを順に改行区切りで出力せよ．

### Sample Explanation 1 $ 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) $ は狭義単調増加列でないことに注意してください． ### 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) $ - 全てのテストケースにおける $ N $ の総和は $ 3\times 10^5 $ 以下 - 入力される数値は全て整数