Problem Statement

You are given $a permutation P=(P_1,\ldots,P_N)$ of $(1,\ldots,N)$, and an integer K.
Find the number of pairs of integers (L, R) that satisfy all of the following conditions:

• $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$

Input

Input is given from Standard Input in the following format:
N K
$P_1 P_2 \ldots P_N$

Output

Print the answer.

Constraints

• $1 \leq N \leq 1.4\times 10^5$
• P is a permutation of $(1,\ldots,N)$.
• $0 \leq K \leq 3$
• All values in input are integers.

Sample Input 1

4 1
1 4 2 3

Sample Output 1

9

The following nine pairs (L, R) satisfy the conditions.

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

For (L,R) = (1,2), we have $\mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3$ and R-L+K=2-1+1 = 2, not satisfying the condition.

Sample Input 2

2 0
2 1

Sample Output 2

3

Sample Input 3

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

Sample Output 3

37

见题面 Input 部分

见题面 Output 部分