给你一个长度为 $n$ 的排列 $p$（一个由 $n$ 个整数组成的数组，其中 $1$ 到 $n$ 的每个数字恰好出现一次）。

如果对于每个 $i$ ($l \le i \le r$)，都满足以下条件中的至少一个，则称一个连续子数组 $[l, r]$ 是反转的（inverted）：

• 存在一个 $j$ ($l \le j \le r$) 满足 $j < i$ 且 $p_j > p_i$；
• 存在一个 $j$ ($l \le j \le r$) 满足 $j > i$ 且 $p_j < p_i$。

你的任务是求出排列 $p$ 的反转子数组的最大可能长度。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 3 \cdot 10^5$)。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)。数组 $p$ 是一个排列。

输入的附加限制：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 排列 $p$ 的反转子数组的最大可能长度（如果不存在这样的子数组，则输出 0）。

样例

输入样例 1

5
3
1 3 2
2
1 2
4
2 1 4 3
5
5 4 3 2 1
7
2 1 3 6 4 5 7

输出样例 1

2
0
4
5
3