这个版本的问题有 $$$n \le 2 \cdot 10^5$$$ 和 $$$a_i \le 10^6$$$ (并且一次测试中输入数据集的 $$$n$$$ 数量也有限制)。
在 VK 期间,Vika 已经在版本控制系统中进行了 $$$n$$$ 提交。第 $$$i$$$ 次提交是在 Vika 在公司工作的第 $$$a_i$$$ 天进行的。在某些日子里,维卡可以做出多次承诺,而在其他日子里,她什么也做不了。
Vika 对连续几天的片段感兴趣,因此在这些天中的每一天她都至少有一次提交。这样的时间段越长,她就会感觉员工的工作效率越高。
最近,Vika 找到了一种方法来提前任何提交的时间,但不超过一天。因此,第 $$$i$$$ 次提交现在可以在第 $$$a_i$$$ 天或第 $$$(a_i + 1)$$$ 天“完成”。每次提交的时间都可以独立于其他提交进行调整 - 特别是,您可以将所有提交保留为原始时间,或者将所有提交恰好提前一天。
找出连续几天中最长可能段的长度,在可能调整某些提交的时间之后,Wiki 将在每一天中在她的个人资料中显示至少一个提交。
输入
每个测试都包含多组输入数据。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 输入数据集的数量。以下是输入数据集的描述。
每个输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) - 提交数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ 按非递减顺序 ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 10^6$$$) - 提交的天数。
保证所有输入数据集的 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每组输入数据,打印一个整数 - 这几天的最大可能长度,在每一天中,Wiki 将在她的个人资料中显示至少一个提交,之后可能会将某些提交的时间向前调整不超过一天。
示例
输入 #1
3 9 1 1 3 4 6 6 6 8 10 6 1 2 3 4 5 6 5 10 10 10 10 10
输出 #1
5 6 2
注意
在第一组输入中,我们可以将 $$$3$$$ 天的提交日期更改为 $$$4$$$ 天,将 $$$4$$$ 天的提交日期更改为 $$$5$$$ 天,并将 $$$6$$$ 天的任何提交日期更改为 $$$7$$$ 天。然后,在 $$$4$$$、$$$5$$$、$$$6$$$、$$$7$$$ 和 $$$8$$$ 的每一天,维基配置文件中都会至少显示一次提交,并且连续提交的最长天数为 $$$[4; 8]$$$ - 长度为$$$5$$$。
在第二组输入中,您可以将所有提交保留原样,也可以将每个提交向前移动一天。无论如何,这段时间的长度将为$$$6$$$。
在第三组输入数据中,Vika 进行了多次提交,但都是在同一天进行的,编号为 $$$10$$$。在最好的情况下,天数跨度将达到 $$$2$$$ 的长度 - 如果一些提交留在 $$$10$$$ 天,而其他提交则移至 $$$11$$$ 天。