题目描述

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

输出子序列的最大长度。

输入格式

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

对于每个测试用例：

• 第一行输入一个整数 $n$ $(1 \le n \le 2 \times 10^6)$。
• 接下来一行 $n$ 个整数，表示 $1$ 到 $n$ 的排列。

数据保证 $\sum n \le 4 \times 10^6$。

输出格式

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

样例

输入

1
7
5 1 3 2 7 4 6

输出

6