Contest Duration: - (local time) (100 minutes) Back to Home
Ex - Beautiful Subsequences /

Time Limit: 6 sec / Memory Limit: 1024 MB

### 問題文

(1,\ldots,N) を並び替えて得られる長さ N の順列 P=(P_1,\ldots,P_N)、及び整数 K が与えられます。

• 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

### 制約

• 1 \leq N \leq 1.4\times 10^5
• P(1,\ldots,N) を並び替えて得られる順列
• 0 \leq K \leq 3
• 入力は全て整数

### 入力

N K
P_1 P_2 \ldots P_N


### 入力例 1

4 1
1 4 2 3


### 出力例 1

9


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

(L,R) = (1,2)\mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3R-L+K=2-1+1 = 2 となるので、条件を満たしません。

### 入力例 2

2 0
2 1


### 出力例 2

3


### 入力例 3

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


### 出力例 3

37


Score : 600 points

### 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


### 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