← 返回题目列表

Codeforces · 1468/A

A. 莱斯

中文机器翻译题面 查看原题

让我们称一个序列 $$$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)。$$$$$$ 特别是,任何不超过两个元素的序列几乎是递增的。

给定一个整数序列 $$$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

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$$$ 已经几乎在增加。