Positive integers $N, K$ and a sequence $A = [A_1, A_2, \cdots, A_{N}]$ of length $N$ are given. The sequence $A$ satisfies the following conditions.

• $1 \leq A_i \leq N$ ($1 \leq i \leq N$).
• $A_i \neq A_j$ ($1 \leq i < j \leq N$).

Find the number of integer pairs $(l, r)$ that satisfy the following conditions.

• $1 \leq l < r \leq N$.
• There exist exactly $K$ integers $t$ such that $l < t < r$ and $\min(A_l, A_r) < A_t < \max(A_l, A_r)$.

The input is given in the following format.

$N \ K$ $A_1 \ A_2 \ \cdots \ A_{N}$

Print the answer on the first line.

• $2 \leq N \leq 70 \ 000$.
• $0 \leq K \leq 7$.
• $1 \leq A_i \leq N$ ($1 \leq i \leq N$).
• $A_i \neq A_j$ ($1 \leq i < j \leq N$).