E - Sparse Range Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

長さ N の整数列 (A_1,\dots,A_N) と正整数 D が与えられます。

以下の条件をともに満たす整数の組 (L,R) の個数を求めてください。

  • 1 \leq L \leq R \leq N
  • (A_L,A_{L+1},\dots,A_R) のどの 2 つの要素も差が D 以上である
    • すなわち、 L \leq i < j \leq R を満たす全ての整数の組 (i,j) について、 |A_i-A_j|\geq D である

制約

  • 2\leq N \leq 4\times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq D \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N D
A_1 \dots A_N

出力

答えを出力せよ。

入力例 1

5 3
3 1 4 1 5

出力例 1

8

(1,1),(2,2),(3,3),(4,4),(5,5),(2,3),(3,4),(4,5) の 8 組が条件を満たします。

入力例 2

9 1
1 2 3 4 5 6 7 8 9

出力例 2

45

入力例 3

6 1000000000
123456789 234567891 987654321 321987654 1000000000 1

出力例 3

6

Score : 450 points

Problem Statement

You are given an integer sequence of length N, (A_1,\dots,A_N), and a positive integer D.

Find the number of pairs of integers (L,R) that satisfy both of the following conditions:

  • 1 \leq L \leq R \leq N
  • Any two elements of (A_L,A_{L+1},\dots,A_R) have a difference of at least D.
    • That is, |A_i-A_j|\geq D for all pairs of integers (i,j) satisfying L \leq i < j \leq R.

Constraints

  • 2\leq N \leq 4\times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq D \leq 10^9

Input

The input is given from Standard Input in the following format:

N D
A_1 \dots A_N

Output

Output the answer.

Sample Input 1

5 3
3 1 4 1 5

Sample Output 1

8

The eight pairs (1,1),(2,2),(3,3),(4,4),(5,5),(2,3),(3,4),(4,5) satisfy the conditions.

Sample Input 2

9 1
1 2 3 4 5 6 7 8 9

Sample Output 2

45

Sample Input 3

6 1000000000
123456789 234567891 987654321 321987654 1000000000 1

Sample Output 3

6