让我们调用一个整数序列 美丽 如果满足以下条件:
- 对于除第一个元素之外的每个元素,左边都有一个元素小于它;
- 对于除最后一个元素之外的每个元素,右侧都有一个比它大的元素;
例如,$$$[1, 2]$$$、$$$[42]$$$、$$$[1, 4, 2, 4, 7]$$$ 和 $$$[1, 2, 4, 8]$$$ 很漂亮,但 $$$[2, 2, 4]$$$ 和 $$$[1, 3, 5, 3]$$$不是。
回想一下,子序列是可以通过删除一些元素(可能为零)从另一个序列获得的序列,而不改变剩余元素的顺序。
给定一个整数数组 $$$a$$$,大小为 $$$n$$$。找到数组 $$$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$$$ 的最长美丽子序列的长度。
示例
输入复制
514251 2 3 4 566 5 4 3 2 171 1 3 4 2 3 462 3 1 1 2 4
输出复制
1 5 1 5 3