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$

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.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \ldots P_N

Output

Print the answer.