CF2075F.Beautiful Sequence Returns

我们称一个整数序列为美丽的，当且仅当其满足以下条件：

• 对于除第一个元素外的每个元素，其左侧存在一个比它小的元素；
• 对于除最后一个元素外的每个元素，其右侧存在一个比它大的元素；

例如，$[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$ 的最长美丽子序列的长度。

翻译由 DeepSeek R1 完成