← 返回题目列表

Codeforces · 549/F

F. Yura 和开发者

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

Yura 有一个由 k 个开发人员组成的团队和一个编号为 1 到 n 的 n 个任务列表。 Yura 将选择本周要完成的一些任务。由于 Looksery 的奇怪习惯,所选任务的数量应该是包含不少于 2 个数字的连续整数段,i。 e.形式为 l, l + 1, ..., r 的序列,其中 1 ≤ l < r ≤ n。

每个任务 i 都有一个与其关联的整数 ai ,表示完成第 i 个任务需要多少工时。开发者一点也不自信,他们实际上害怕困难的任务。知道这一点后,尤拉决定挑选一个最难的任务(需要最多工时完成的任务,在几个相同难度的最难任务中任意选择一个)并自己完成。因此,如果选择了编号为 [l, r] 的任务,那么开发人员就剩下 r - l 任务需要自己完成。

每个开发人员可以在任何任务上花费任意整数小时,但是当他们完成整个任务时,应该在第 i 个任务上花费正好 ai 个工时。

开发人员的最后一个但并非最不重要的问题是,如果一个人比另一位开发人员工作更多,他就会生气。如果可以找到这样的工作分配,允许完成所有任务并且让每个开发人员工作相同的时间(Yura 执行的工作量对其他工人和他来说并不重要),则一组任务 [l, r] 被认为是好的。

例如,假设 Yura 选择了具有以下难度的任务:a = [1, 2, 3, 4],并且他有 3 个开发人员可供使用。他独自完成了最难的第四个任务,而开发人员则面临着困难的任务[1,2,3]。如果第一个开发人员在第一个任务上花费一个小时,在第三个任务上花费一个小时,第二个开发人员在第二个任务上花费两个小时,第三个开发人员在第三个任务上花费两个小时,那么他们就完成了,因为每个开发人员都工作了两个小时,并且每个任务都已经完成了所需的时间。作为另一个示例,如果第一个任务需要两个小时而不是一个小时才能完成,则不可能以上述方式分配任务。

除了工作之外,Yura 还喜欢解决问题。他想知道有多少对 (l, r) (1 ≤ l < r ≤ n) 使得线段 [l, r] 是好的? Yura已经解决了这个问题,但是他没有时间写代码。请帮助 Yura 实施该问题的解决方案。

输入

输入的第一行包含两个正整数:n和k(1 ≤ n ≤ 300 000, 1 ≤ k ≤ 1 000 000),列表中的任务数量和Yura可支配的开发人员数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 109)。

输出

输出单个整数 — 满足语句中条件的对 (l, r) 的数量。

示例

输入 #1

4 3
1 2 3 4

输出 #1

3

输入 #2

4 2
4 4 7 4

输出 #2

6

注意

在第一个示例中,有三个好的片段:

1. [1;3] — 最困难的任务需要 3 个工时,因此剩下的任务需要 1 和 2 个工时。解决方案是让第一个开发人员在第一个任务上工作一个小时,而第二个和第三个开发人员在第二个任务上工作。每个开发人员正好工作一小时。
2. [1;4] — 最困难的任务需要 4 个工时,因此剩下的任务需要 1、2 和 3 个工时。如果第一个开发人员在第一个任务上花费一个小时,在第三个任务上花费一个小时,第二个开发人员在第二个任务上花费两个小时,第三个开发人员在第三个任务上花费两个小时,那么他们就完成了,因为每个开发人员都工作了两个小时。
3. [3;4] — 最难的任务需要 4 个工时,因此只剩下一项任务需要 3 个工时。一个解决方案是让每个开发人员工作一个小时。