CF1769C2 Подкрутка II

在本题的版本中，$ n \le 2 \cdot 10^5 $ 且 $ a_i \le 10^6 $（同时对于同一测试中的所有输入数据，$ n $ 的总和也有限制）。 Vika 在 VK 公司工作期间已经完成了 $ n $ 次提交。第 $ i $ 次提交是在她工作的第 $ a_i $ 天完成的。在某些天，Vika 可能会有多次提交，而在其他天则可能没有任何提交。 Vika 对于这样的连续若干天区间感兴趣：在这些天中的每一天，她都至少有一次提交。最长的这类区间越长，她就会觉得自己越高产。 最近，Vika 找到了一个方法，可以将任意一次提交的时间向后调整，但最多只能向后推迟一天。也就是说，第 $ i $ 次提交现在可以被视为发生在第 $ a_i $ 天，或者第 $ (a_i + 1) $ 天。每次提交的时间可以独立调整——特别地，可以选择所有提交都不调整，也可以选择所有提交都统一向后推迟一天。 请你计算，在对某些提交的时间进行不超过一天的调整后，Vika 的个人资料中，每天至少有一次提交的最长连续天数区间的最大可能长度。

每个测试包含若干组输入数据。第一行包含一个整数 $ 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 $。

对于每组输入数据，输出一个整数，表示在对某些提交的时间进行不超过一天的调整后，Vika 的个人资料中每天至少有一次提交的最长连续天数区间的最大可能长度。

由 ChatGPT 4.1 翻译