题目描述

すぬけくんは、$(0,1,\cdots,N-1)$ の順列 $(P_0,P_1,\cdots,P_{N-1})$ を持っています。

すぬけくんは、以下の操作をちょうど $1$ 回だけ行います。

• $P$ の連続する $K$ 要素を選び、それらを昇順に並び替える。

操作後の $P$ としてありうる順列の個数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $P_0$ $P_1$ $\cdots$ $P_{N-1}$

输出格式

操作後の $P$ としてありうる順列の個数を出力せよ。

题目大意

给定$n,k$，再给定一个$0$到$n-1$的排列$p_1,p_2,\dots,p_n$。你可以进行恰好一次如下操作：

• 选定一个长度恰为$k$的区间$[l,r]$，把$p_l,p_{l+1},\dots,p_r$升序排序，其他位置不变。

试问可能的不同结果序列有多少种。

$2\le n\le 2\times 10^5, 2\le k\le n$

Translated by Caro23333

5 3
0 2 1 4 3

2

4 4
0 1 2 3

1

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

6

提示

制約

• $2\ \leq\ N\ \leq\ 200000$
• $2\ \leq\ K\ \leq\ N$
• $0\ \leq\ P_i\ \leq\ N-1$
• $P_0,P_1,\cdots,P_{N-1}$ はすべて異なる。
• 入力される値はすべて整数である。

Sample Explanation 1

操作後の $P$ としてありうる順列は、$(0,1,2,4,3),(0,2,1,3,4)$ の $2$ 個です。