普切廖诺克与区间

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的正整数数组 $a$。你需要选择 $k$ 个两两不相交的区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$，满足：

• 第 $i$ 个区间的长度为 $k-i+1$；
• 对任意 $i<j$，有 $r_i<l_j$；
• 各区间元素和严格递增。

求最大的可行 $k$。

输入格式

第一行输入测试用例数量 $t$。

每个测试用例的第一行输入整数 $n$，第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示最大的可行 $k$。

样例输入 1

5
1
1
3
1 2 3
5
1 1 2 2 3
7
1 2 1 1 3 2 6
5
9 6 7 9 7

样例输出 1

1
1
2
3
1

数据范围

对于所有数据，$1\le t\le100$，$1\le n\le100000$，$1\le a_i\le10^9$，且单个输入文件中所有测试用例的 $n$ 之和不超过 $100000$。