← 返回题目列表

AtCoder · abc248_h

Ex. 美丽的后续

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

分数: 600 点

问题陈述

给你一个排列 P=(P_1,\ldots,P_N) of (1,\ldots,N),和一个整数 K.

查找整数对的数量 (L, R) 满足以下所有条件:

  • 1 \leq L \leq R \leq N

  • \mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R) \leq R - L + K

约束

  • 1 \leq N \leq 1.4\times 10^5
  • P 是一个排列 (1,\ldots,N).
  • 0 \leq K \leq 3
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
P_1 P_2 \ldots P_N

输出

打印答案。


示例输入 1

4 1
1 4 2 3

示例输出 1

9

以下九对 (L, R) 满足条件。

  • (1,1)
  • (1,3)
  • (1,4)
  • (2,2)
  • (2,3)
  • (2,4)
  • (3,3)
  • (3,4)
  • (4,4)

对于 (L,R) = (1,2),我们有 \mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3 和 R-L+K=2-1+1 = 2,不满足条件。


示例输入 2

2 0
2 1

示例输出 2

3

示例输入 3

10 3
3 7 10 1 9 5 4 8 6 2

示例输出 3

37