CF1468A LaIS

我们称一个序列 $b_1, b_2, b_3, \dots, b_{k-1}, b_k$ 为“几乎递增”的，如果满足 $ \min(b_1, b_2) \le \min(b_2, b_3) \le \dots \le \min(b_{k-1}, b_k) $。特别地，任何长度不超过 $2$ 的序列都是“几乎递增”的。 给定一个整数序列 $a_1, a_2, \dots, a_n$，请计算其最长“几乎递增”子序列的长度。 你将会得到 $t$ 组测试数据。请你分别独立地解决每组测试数据。 提示：子序列是指可以通过删除原序列中的某些元素（可以不连续），且不改变剩余元素顺序而得到的序列。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^5$），表示序列 $a$ 的长度。 每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示该序列本身。 保证所有测试数据中 $n$ 的总和不超过 $5 \cdot 10^5$。

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

在第一个测试数据中，一个最优的答案是子序列 $1, 2, 7, 2, 2, 3$。 在第二组和第三组测试数据中，整个序列 $a$ 已经是“几乎递增”的。 由 ChatGPT 4.1 翻译