← 返回题目列表

AtCoder · awc0026_e

E. 恰到好处的温差

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

分数: 466 分

问题陈述

高桥在气象观测站工作,正在记录超过 N 特定区域的天数。当日最高气温 i (1 \leq i \leq N) 是 A_i ℃.

Takahashi 希望选择连续的天数间隔并检查温度波动范围。从一天开始的一个时间间隔 l 到今天 r (1 \leq l \leq r \leq N),该区间的“波动范围”定义为:

\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r)

特别是,当 l = r (仅包含一天的区间),波动范围为 0.

给定一个正整数 N,一个非负整数 K,以及一系列最高温度 N 天 A_1, A_2, \dots, A_N,找出波动范围恰好为的区间数 K。即求整数对的个数 (l, r) (1 \leq l \leq r \leq N)满足:

\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r) = K

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • -10^9 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N K
A_1 A_2 \dots A_N

第一行包含一个正整数 N 表示天数,非负整数 K 代表指定的波动范围,以空格分隔。第二行包含整数 A_1, A_2, \dots, A_N 代表每天的最高气温,以空格分隔。

输出

输出对数 (l, r) 其波动范围恰好是 K,在一行上。


示例输入 1

5 3
1 4 2 5 3

示例输出 1

6

示例输入 2

7 0
3 3 3 5 5 3 3

示例输出 2

12

示例输入 3

10 5
2 -1 3 7 4 0 6 1 5 -2

示例输出 3

2