子序列

Problem Description

给你一个长度为 $n$ 的排列，你需要从中选出一个最长的子序列（注意是子序列不是子串），满足该子序列中两端的值大于中间的所有值。 输出子序列的最大长度。

Input

第一行输入一个整数 $T$ （$1 \le T \le 50$），表示测试的总数。 对于每个测试用例，第一行输入一个整数 $n$（$1 \le n \le 2*10^6$）。 接来下一行 $n$ 个整数，表示 $1$ 到 $n$ 的排列。 数据保证 $\Sigma n \leq 4 \times 10^6$

Output

对于每个测试用例，输出一个数表示答案。

Sample Input

1
7
5 1 3 2 7 4 6

Sample Output

6

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）