#90 arraycount4

Loading problem...

Preparing the statement, recent submissions, and submit form.

Statement

양의 정수 $N, K$ 와 길이가 $N$ 인 수열 $A = [A_1, A_2, \cdots, A_{N}]$ 이 주어진다. 수열 $A$ 는 다음 조건을 만족한다.

이때, 다음 조건을 만족하는 정수 순서쌍 $(l, r)$ 의 개수를 구하여라.

$1 \leq l < r \leq N$ .
$l < t < r$ 이고 $\min(A_l, A_r) < A_t < \max(A_l, A_r)$ 인 정수 $t$ 가 정확히 $K$ 개 존재한다.

입력은 다음과 같은 형식으로 주어진다.

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

첫째 줄에 정답을 출력한다.

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