大小為 $n$ 的排列，是指由 $n$ 個整數 $a_1,a_2,\ldots,a_n$ 組成的序列，其中從 $1$ 到 $n$ 的每個值都恰好出現一次。

若可以從序列 $a_1,a_2,\ldots,a_n$ 中刪除一些元素得到序列 $b_1,b_2,\ldots,b_l$，則稱 $b$ 是 $a$ 的子序列（也就是說，$l\le n$，且存在 $i_1<i_2<\ldots<i_l$，使得 $a_{i_t}=b_t$）。

• 若序列中的元素 $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$。你需要將它分成兩個非空子序列 $q$ 和 $r$。換句話說，$p$ 的每個元素都必須恰好屬於其中一個子序列。你需要最大化 $q$ 中紀錄的個數與 $r$ 中反紀錄的個數之和。

輸入格式

每個測試包含多組資料。第一行包含一個整數 $t$（$1\le t\le100\,000$），表示資料組數。接下來的 $2t$ 行描述這些資料。

每組資料的第一行包含一個整數 $n$，表示排列的大小（$2\le n\le200\,000$）。

每組資料的第二行包含 $n$ 個整數 $p_1,p_2,\ldots,p_n$，表示原排列。保證 $p$ 的元素中，從 $1$ 到 $n$ 的每個數都恰好出現一次。

所有資料的 $n$ 之和不超過 $200\,000$。

輸出格式

對每組資料，輸出一個整數，表示最佳劃分中 $q$ 的紀錄個數與 $r$ 的反紀錄個數之和的最大可能值。

子任務

以 $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}$

第二組資料中，將 $p$ 最佳劃分為 $q$ 和 $r$ 的一種方式如下：

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