CF1118D2 Coffee and Coursework (Hard Version)

本题的简单版与困难版的唯一区别在于数据范围。 Polycarp 需要写一份课程作业，这份作业共有 $m$ 页。 Polycarp 有 $n$ 杯咖啡。第 $i$ 杯咖啡中含有 $a_i$ 单位的咖啡因。Polycarp 可以喝任意几杯咖啡（每杯最多喝一次），且可以按任意顺序饮用。每杯咖啡必须一次性喝完，不能分多天饮用。 显然，课程作业不可能一天就写完（至少在 Berland 的理想世界中是这样）。 我们来考虑 Polycarp 某一天的工作情况。假设这一天他喝了 $k$ 杯咖啡，这些咖啡的咖啡因含量分别为 $a_{i_1}, a_{i_2}, \dots, a_{i_k}$。那么，他喝的第一杯咖啡能让他写 $a_{i_1}$ 页作业，第二杯能让他写 $\max(0, a_{i_2} - 1)$ 页，第三杯能让他写 $\max(0, a_{i_3} - 2)$ 页，……，第 $k$ 杯能让他写 $\max(0, a_{i_k} - k + 1)$ 页。 如果某一天 Polycarp 没有喝咖啡，那么这一天他无法写作业。 Polycarp 希望尽快完成作业（即用最少的天数完成）。你的任务是求出他完成作业所需的最少天数，或者判断是否无法完成。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \times 10^5$，$1 \le m \le 10^9$），分别表示咖啡的杯数和作业的页数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示第 $i$ 杯咖啡的咖啡因含量。

如果无法完成作业，输出 $-1$。否则输出 Polycarp 完成作业所需的最少天数。

在第一个样例中，Polycarp 可以第一天喝第四杯（写 $1$ 页），第二天喝第一和第二杯（写 $2 + (3 - 1) = 4$ 页），第三天喝第五杯（写 $2$ 页），第四天喝第三杯（写 $1$ 页），所以答案是 $4$。显然无法在三天或更少天数内完成作业。 在第二个样例中，Polycarp 可以第一天喝第三、第四和第二杯（写 $4 + (2 - 1) + (3 - 2) = 6$ 页），第二天喝第六杯（写 $4$ 页），所以答案是 $2$。显然无法在一天内完成全部作业。 在第三个样例中，Polycarp 可以第一天喝完所有咖啡，写 $5 + (5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 15$ 页作业。 在第四个样例中，Polycarp 不能在第一天喝完所有咖啡，必须有一杯留到第二天喝。第一天可以写 $5 + (5 - 1) + (5 - 2) + (5 - 3) = 14$ 页，第二天写 $5$ 页，这样就足够了。 在第五个样例中，即使每天只喝一杯咖啡，也无法完成全部作业，所以答案是 $-1$。 由 ChatGPT 4.1 翻译