大きさ $n$ の順列とは、$1$ から $n$ までのすべての値がちょうど一度ずつ現れる、$n$ 個の整数からなる列 $a_1,a_2,\ldots,a_n$ のことです。

列 $b_1,b_2,\ldots,b_l$ が列 $a_1,a_2,\ldots,a_n$ の部分列であるとは、$a$ からいくつかの要素を削除して $b$ を得られることをいいます（すなわち、$l\le n$ であり、$a_{i_t}=b_t$ を満たす $i_1<i_2<\cdots<i_l$ が存在することです）。

• 列の要素 $a_i$ がそれより前のすべての要素より真に大きいとき（すなわち、すべての $1\le j<i$ について $a_j<a_i$ のとき）、その要素を記録と呼びます。
• 列の要素 $a_i$ がそれより前のすべての要素より真に小さいとき（すなわち、すべての $1\le j<i$ について $a_j>a_i$ のとき）、その要素を反記録と呼びます。

大きさ $n$ の順列 $p_1,p_2,\ldots,p_n$ が与えられます。これを、空でない 2 つの部分列 $q$ と $r$ に分割してください。つまり、$p$ の各要素はちょうど一方の部分列に入る必要があります。このとき、$q$ の記録の個数と $r$ の反記録の個数の和を最大化してください。

入力

各テストは複数のテストケースからなります。最初の行には、テストケース数を表す整数 $t$（$1\le t\le100\,000$）が 1 つ与えられます。続く $2t$ 行にはテストケースの記述が与えられます。

各テストケースの記述の最初の行には、順列の大きさを表す整数 $n$（$2\le n\le200\,000$）が 1 つ与えられます。

各テストケースの記述の 2 行目には、元の順列を表す $n$ 個の整数 $p_1,p_2,\ldots,p_n$ が与えられます。$p$ の要素には、$1$ から $n$ までの各数がちょうど一度ずつ現れることが保証されます。

すべてのテストケースにわたる $n$ の総和は $200\,000$ 以下です。

出力

各テストケースについて、最適な分割における $q$ の記録の個数と $r$ の反記録の個数の和として取りうる最大値を表す整数を 1 つ出力してください。

小課題

1 つのテストに含まれるすべてのテストケースの $n$ の値の総和を $N$ とします。

入出力例

入力 1

4
5
4 1 2 3 5
10
3 8 10 4 1 2 7 9 5 6
3
1 2 3
6
4 2 5 1 6 3

出力 1

5
6
3
5

注記

最初のテストケースにおける、$p$ を $q$ と $r$ に最適に分割する方法の一例は次のとおりです（$q$ の記録と $r$ の反記録を枠で囲んであります）。

• $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
• $r=\boxed{4}$

2 番目のテストケースにおける、$p$ を $q$ と $r$ に最適に分割する方法の一例は次のとおりです。

• $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
• $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$