Migrated from Lutece 3143 二重之虹

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

本题时间限制改为 300ms，请注意程序运行的常数因子

听说雨过天晴后会有双彩虹。

今后也请大家多多关注 Popipa

---

我们定义一个长为 $n$ 的序列 $A=\{a_1, a_2, \dots, a_n\}$ 是一个 rainbow 序列当且仅当 $n\le 2$，或者

$$\forall i=2, 3,\dots, n-1,\ a_i-a_{i-1}>a_{i+1}-a_i $$

现在有一个长度为 $n$ 的序列 $R=\{r_1, r_2,\dots, r_n\}$，求出 $R$ 的所有满足是 rainbow 的子序列（即不必在 $R$ 中连续）长度的最大值。

Input

输入数据的第一行有一个数字 $T\ (1\le T\le100)$，表示有 $T$ 组数据。

对于每组数据，第一行有一个数字 $n\ (1\le n\le6000)$，表示序列 $R$ 的长度，紧接着下一行有 $n$ 个由空格分割的数字 $r_1, r_2,\dots, r_n\ (|r_i|\le10^{12})$，表示序列 $R$。

Output

对于每一组输入数据，输出一行一个整数，即序列 $R$ 的所有是 rainbow 的子序列长度的最大值。

Samples

2
5
1 2 3 4 5
5
1 2 3 2 1

3
4

Constraints

$1\le T\le100$ $1\le n\le6000$ $|r_i|\le10^{12}$

保证同一测试点中的 $n$ 的和不大于 $6000$。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming