题目描述

我们称一个序列 $b_1, b_2, b_3, \ldots, b_{k-1}, b_k$ 为几乎递增的，如果满足：

$$ \min(b_1, b_2) \leq \min(b_2, b_3) \leq \cdots \leq \min(b_{k-1}, b_k) $$

特别地，任何长度不超过 2 的序列都是几乎递增的。

给定一个整数序列 $a_1, a_2, \ldots, a_n$，请计算其最大几乎递增子序列的长度。

你将会得到 $t$ 组测试数据。请你分别独立地处理每组测试数据。

提示： 子序列是指可以通过删除原序列中的某些元素（可以不连续），且不会改变剩余元素顺序而得到的序列。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 1000$)，表示测试数据数目。

每组测试数据的第一行包含一个整数 $n$ ($2 \leq n \leq 5 \cdot 10^5$)，表示序列 $a$ 的长度。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$)，表示该序列本身。

保证所有测试数据中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示最大几乎递增子序列的长度。

输入输出样例 #1

输入 #1

3
8
1 2 7 3 2 1 2 3
2
2 1
7
4 1 5 2 6 3 7

输出 #1

6
2
7

说明/提示

在第一个测试数据中，一个最优的答案是子序列 $1, 2, 7, 2, 2, 3$。

在第二组和第三组测试数据中，整个序列 $a$ 已经是几乎递增的。

数据范围

$20\%$ 的数据：$\sum n \leq 10^2$。

$40\%$ 的数据：$\sum n \leq 10^4$。

另有 $20\%$ 的数据：满足 $\sum n \leq 10^4$，$a_i \leq 100$。

另有 $20\%$ 的数据：满足 $\sum n \leq 3 \times 10^5$，$a_i \leq 1000$。

对于 $100\%$ 的数据：满足 $\sum n \leq 5 \times 10^5$，$1 \leq a_i \leq n$。