Вам надано перестановку \(P=(P_1,\ldots,P_N)\) з \((1,\ldots,N)\) і ціле число \(K\).

Знайдіть кількість пар цілих чисел (\(L, R\)), які задовольняють усі наступні умови:

• \(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\)

Наступний  рядок містить \(N\) цілих чисел \(P_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

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

Приклад вхідних даних

4 1
1 4 2 3

Приклад вихідних даних

9

Приклад вхідних даних

2 0
2 1

Приклад вихідних даних

3

Приклад вхідних даних

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

Приклад вихідних даних

37