题目描述

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

输出子序列的最大长度。

输入格式

第一行输入一个整数 $T$ （$1 \le T \le 50$），表示测试的总数。

对于每个测试用例，第一行输入一个整数 $n$（$1 \le n \le 2*10^6$）。

接来下一行 $n$ 个整数，表示 $1$ 到 $n$ 的排列。

数据保证 $\Sigma n \leq 4 \times 10^6$

输出格式

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

1
7
5 1 3 2 7 4 6

6