I. 子序列

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个长度为 $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