Đoạn ổn định (Stable Subarray)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $A$ gồm $N$ số nguyên:

$$a_1,a_2,\ldots,a_N.$$

Với hai chỉ số $l,r$ thỏa mãn $1 \le l \le r \le N$, dãy

$$a_l,a_{l+1},\ldots,a_r$$

được gọi là một đoạn con liên tiếp của $A$ và được ký hiệu là $[l,r]$.

Đoạn $[l,r]$ được gọi là ổn định nếu hiệu giữa giá trị lớn nhất và giá trị nhỏ nhất xuất hiện trong đoạn không vượt quá $K$, tức là:

$$\max_{l\le i\le r} a_i-\min_{l\le i\le r} a_i\le K.$$

Hai đoạn có cặp chỉ số $(l,r)$ khác nhau được tính là hai đoạn khác nhau, kể cả khi các giá trị xuất hiện trong hai đoạn hoàn toàn giống nhau.

Hãy xác định tổng số đoạn con liên tiếp ổn định của dãy $A$.

Input

• Dòng đầu chứa hai số nguyên $N$ và $K$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\ldots,a_N$.

Output

In ra một số nguyên duy nhất là số đoạn con liên tiếp ổn định của dãy $A$.

Subtask

• Subtask 1: $1 \le N \le 200$; $0 \le K \le 2\cdot10^9$; $|a_i|\le10^9$.
• Subtask 2: $1 \le N \le 5000$; $0 \le K \le 2\cdot10^9$; $|a_i|\le10^9$.
• Subtask 3: $1 \le N \le 5\cdot10^4$; $0 \le K \le 2\cdot10^9$; $|a_i|\le10^9$.
• Subtask 4: $1 \le N \le 2\cdot10^5$; $0 \le K \le 2\cdot10^9$; $|a_i|\le10^9$.

Ví dụ

Ví dụ 1

Input

5 2
1 3 2 5 4

Output

9

Giải thích

Có đúng $9$ đoạn ổn định:

$$[1,1],\ [1,2],\ [1,3],\ [2,2],\ [2,3],\ [3,3],\ [4,4],\ [4,5],\ [5,5].$$

Chẳng hạn, trên đoạn $[1,3]$ ta có các giá trị $1,3,2$, nên giá trị lớn nhất là $3$, giá trị nhỏ nhất là $1$ và:

$$3-1=2\le K.$$

Trong khi đó, đoạn $[3,4]$ chứa các giá trị $2,5$, có độ chênh lệch:

$$5-2=3>K,$$

nên không ổn định.

Ví dụ 2

Input

4 0
7 7 7 7

Output

10

Giải thích

Mọi phần tử của dãy đều bằng $7$. Vì vậy, với mọi đoạn con:

$$\max a_i-\min a_i=7-7=0\le K.$$

Do đó cả

$$\frac{4\cdot5}{2}=10$$

đoạn con liên tiếp của dãy đều ổn định.

Ví dụ 3

Input

3 3
1 5 9

Output

3

Giải thích

Ba đoạn gồm một phần tử $[1,1]$, $[2,2]$ và $[3,3]$ đều có độ chênh lệch bằng $0$ nên ổn định.

Mọi đoạn chứa ít nhất hai phần tử đều không ổn định. Chẳng hạn:

• đoạn $[1,2]$ có độ chênh lệch $5-1=4>3$;
• đoạn $[2,3]$ có độ chênh lệch $9-5=4>3$;
• đoạn $[1,3]$ có độ chênh lệch $9-1=8>3$.

Vì vậy đáp án là $3$.