F. 美丽序列返回

每个测试的时间限制：2 秒
内存限制：256 兆字节

如果一个整数序列满足以下条件，则称其为 美丽序列：

• 除了第一个元素外，每个元素的左边都存在一个比它小的元素；
• 除了最后一个元素外，每个元素的右边都存在一个比它大的元素。

例如，$[1,2]$，$[42]$，$[1,4,2,4,7]$ 和 $[1,2,4,8]$ 都是美丽序列，但 $[2,2,4]$ 和 $[1,3,5,3]$ 不是。

回顾：子序列是通过从原序列中删除若干元素（可能为零）而不改变剩余元素的顺序得到的序列。

给定一个长度为 $n$ 的整数数组 $a$。找出数组 $a$ 的 最长美丽子序列 并输出它的长度。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。接下来是 $t$ 个独立的测试用例。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）—— 数组 $a$ 的长度。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）—— 数组 $a$ 的元素。

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

输出
对于每个测试用例，输出一个整数 —— 数组 $a$ 的最长美丽子序列的长度。

示例

输入：

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

输出：

1
5
1
5
3