#90 arraycount4

Loading problem...

Preparing the statement, recent submissions, and submit form.

#90 arraycount4 | DOJ

Statement

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.

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.

Sample 1

Input

5 0
1 3 5 2 4

Output

Sample 2

Input

6 1
6 2 5 1 4 3

Output

Sample 3

Input

6 2
1 2 3 4 5 6

Output