Array and Counting 4

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

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

이때, 다음 조건을 만족하는 정수 순서쌍 $(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}$

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

• $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$).